Submission #339039

#TimeUsernameProblemLanguageResultExecution timeMemory
339039sinamhdvDango Maker (JOI18_dango_maker)C++11
100 / 100
648 ms161516 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1000 * 1000 * 1000; const ll LINF = (ll)INF * INF; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod) #define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod) #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 3050 int n, m; char grid[MAXN][MAXN]; int dirs[MAXN][MAXN]; int dp[3][MAXN][MAXN]; inline void filldp(int x, int y) { dp[0][x][y] = max(dp[0][x - 1][y + 1], max(dp[1][x - 1][y + 1], dp[2][x - 1][y + 1])); if (dirs[x][y] & 2) dp[2][x][y] = dp[0][x][y] + 1; if (dirs[x][y] & 1) dp[1][x][y] = max(dp[1][x - 1][y + 1], max(dp[0][x - 2][y + 2], dp[1][x - 2][y + 2])) + 1; } int32_t main(void) { fast_io; cin >> n >> m; FOR(i, 0, n) { FOR(j, 0, m) { cin >> grid[i][j]; } } FOR(i, 0, n) { FOR(j, 0, m) { if (grid[i][j] == 'R' && grid[i][j + 1] == 'G' && grid[i][j + 2] == 'W') dirs[i + 1][j + 1] |= 1; if (grid[i][j] == 'R' && grid[i + 1][j] == 'G' && grid[i + 2][j] == 'W') dirs[i + 1][j + 1] |= 2; } } FOR(i, 1, m + 1) { dp[1][1][i] = dirs[1][i] & 1; dp[2][1][i] = ((dirs[1][i] & 2) > 0); } FOR(i, 2, n + 1) { dp[2][i][m] = ((dirs[i][m] & 2) > 0); } FOR(i, 2, m + 1) { for (int x = 2, y = i - 1; x <= n && y > 0; x++, y--) { filldp(x, y); } } FOR(i, 2, n + 1) { for (int x = i + 1, y = m - 1; x <= n && y > 0; x++, y--) { filldp(x, y); } } int ans = 0; FOR(i, 1, n + 1) { ans += max(dp[0][i][1], max(dp[1][i][1], dp[2][i][1])); } FOR(i, 2, m + 1) { ans += max(dp[0][n][i], max(dp[1][n][i], dp[2][n][i])); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...