Submission #634684

#	Time	Username	Problem	Language	Result	Execution time	Memory
634684		colossal_pepe	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	374 ms	10680 KiB

dango_maker

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<string> g;

vector<pair<int, int>> getDiagonalCoords(int i, int j) {
    vector<pair<int, int>> ret;
    while (i < n and j > -1) {
        ret.push_back({i, j});
        i++, j--;
    }
    return ret;
}

int solve(int bad, int idx, vector<vector<int>> &dp, vector<pair<int, int>> &coords) {
    if (idx >= coords.size()) return 0;
    if (dp[bad][idx] != -1) return dp[bad][idx];
    int i = coords[idx].first, j = coords[idx].second;
    int &ret = dp[bad][idx];
    ret = solve(max(0, bad - 1), idx + 1, dp, coords);
    if (i + 2 < n and g[i][j] == 'R' and g[i + 1][j] == 'G' and g[i + 2][j] == 'W') {
        ret = max(ret, 1 + solve(2, idx + 1, dp, coords));
    }
    if (not bad and j + 2 < m and g[i][j] == 'R' and g[i][j + 1] == 'G' and g[i][j + 2] == 'W') {
        ret = max(ret, 1 + solve(0, idx + 1, dp, coords));
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> g[i];
    }
    int ans = 0;
    for (int j = 0; j < m; j++) {
        vector<pair<int, int>> coords = getDiagonalCoords(0, j);
        vector<vector<int>> dp(3, vector<int>(coords.size(), -1));
        ans += solve(0, 0, dp, coords);
    }
    for (int i = 1; i < n; i++) {
        vector<pair<int, int>> coords = getDiagonalCoords(i, m - 1);
        vector<vector<int>> dp(3, vector<int>(coords.size(), -1));
        ans += solve(0, 0, dp, coords);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int solve(int, int, std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >&)':
dango_maker.cpp:18:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (idx >= coords.size()) return 0;
      |         ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67