제출 #532554

#제출 시각아이디문제언어결과실행 시간메모리
532554rk42745417Dango Maker (JOI18_dango_maker)C++17
33 / 100
4 ms2764 KiB
#include <bits/stdc++.h> using namespace std; #define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0); using ll = int64_t; using uint = uint32_t; using ull = uint64_t; using ld = long double; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-8; const ll LINF = ll(4e18) + ll(2e15); static int LamyIsCute = []() { EmiliaMyWife return 48763; }(); const int N = 11; int mpow[N], dp[N][59049], n, m; string arr[N]; void go(int x, int y, int cur, int nxt_bit, int v) { if(cur == m) { dp[x + 1][nxt_bit] = max(dp[x + 1][nxt_bit], v); return; } if(arr[x][cur] == 'R') { go(x, y, cur + 1, nxt_bit + mpow[cur], v); if(cur + 2 < m && arr[x][cur + 1] == 'G' && arr[x][cur + 2] == 'W') go(x, y, cur + 3, nxt_bit, v + 1); } if(arr[x][cur] == 'G') { int r = y / mpow[cur] % 3; if(r == 1) go(x, y, cur + 1, nxt_bit + 2 * mpow[cur], v); else go(x, y, cur + 1, nxt_bit, v); } if(arr[x][cur] == 'W') { int r = y / mpow[cur] % 3; go(x, y, cur + 1, nxt_bit, v + (r == 2)); } } signed main() { cin >> n >> m; mpow[0] = 1; for(int i = 1; i <= m; i++) mpow[i] = mpow[i - 1] * 3; for(int i = 0; i < n; i++) cin >> arr[i]; for(int i = 0; i <= n; i++) for(int j = 0; j < mpow[m]; j++) dp[i][j] = -INF; { int r = 0; for(int j = 0; j < m; j++) if(arr[0][j] == 'R') r += mpow[j]; dp[0][r] = 0; } for(int i = 0; i < n; i++) for(int j = 0; j < mpow[m]; j++) if(dp[i][j] != -INF) go(i, j, 0, 0, dp[i][j]); int ans = 0; for(int j = 0; j < mpow[m]; j++) ans = max(ans, dp[n][j]); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...