Submission #1109046

#TimeUsernameProblemLanguageResultExecution timeMemory
1109046codexistentDango Maker (JOI18_dango_maker)C++14
100 / 100
343 ms172684 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define MAXNM 3005 #define FOR(i, a, b) for(ll i = a; i <= b; i++) const int N = 3005, MOD = 998244353, M = 3e6 + 12; char g[N][N]; int n, m, ok[N][N][2], dp[N * 2][3]; vector<array<int, 2>> e[N * 2]; int main(){ cin >> n >> m; FOR(i, 1, n){ string s; cin >> s; FOR(j, 1, m) g[i][j] = s[j - 1]; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(g[i][j] == 'G' && g[i][j - 1] == 'R' && g[i][j + 1] == 'W') { ok[i][j][0] = 1; } if(g[i][j] == 'G' && g[i - 1][j] == 'R' && g[i + 1][j] == 'W') { ok[i][j][1] = 1; } e[i + j].push_back({i, j}); } } int r = 0; for(int i = 1; i <= n + m; i++) { int f = (int)e[i].size() - 1; if(e[i].empty()) continue; dp[0][0] = ok[e[i][0][0]][e[i][0][1]][0]; dp[0][1] = ok[e[i][0][0]][e[i][0][1]][1]; dp[0][2] = 0; for(int j = 1; j < (int)e[i].size(); j++) { int x = e[i][j][0], y = e[i][j][1]; dp[j][2] = max({dp[j - 1][0], dp[j - 1][1], dp[j - 1][2]}); dp[j][0] = max(dp[j - 1][0], dp[j - 1][2]) + ok[x][y][0]; dp[j][1] = max(dp[j - 1][1], dp[j - 1][2]) + ok[x][y][1]; } // cout << dp[f][1] << '\n'; r += max({dp[f][0], dp[f][1], dp[f][2]}); } cout << r << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...