Submission #1178836

#TimeUsernameProblemLanguageResultExecution timeMemory
1178836MongHwaGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
0 / 100
0 ms324 KiB
#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #include <iostream> #include <vector> using namespace std; #define INF 0x7f7f7f7f int r, g, y; vector<int> rv, gv, yv; int dp[405][405][405][3]; int go(int rcnt, int gcnt, int ycnt, int pre) { if(rcnt == r-1 && gcnt == g-1 && ycnt == y-1) return 0; int& ret = dp[rcnt][gcnt][ycnt][pre]; if(ret != -1) return ret; ret = INF; int val1 = 0, val2 = 0, val3 = 0; if(rcnt+1 < r) { for(int i = 0; i < gcnt; i++) if(rv[rcnt] < gv[i]) val1++; for(int i = 0; i < ycnt; i++) if(rv[rcnt] < yv[i]) val1++; } if(gcnt+1 < g) { for(int i = 0; i < rcnt; i++) if(gv[gcnt] < rv[i]) val2++; for(int i = 0; i < ycnt; i++) if(gv[gcnt] < yv[i]) val2++; } if(ycnt+1 < y) { for(int i = 0; i < rcnt; i++) if(yv[ycnt] < rv[i]) val3++; for(int i = 0; i < gcnt; i++) if(yv[ycnt] < gv[i]) val3++; } if(pre == 0) { if(gcnt+1 < g) ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2))); if(ycnt+1 < y) ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3))); } else if(pre == 1) { if(rcnt+1 < r) ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1))); if(ycnt+1 < y) ret = min(ret, go(rcnt, gcnt, ycnt+1, 2) + abs(rcnt+gcnt+ycnt-(yv[ycnt]+val3))); } else { if(rcnt+1 < r) ret = min(ret, go(rcnt+1, gcnt, ycnt, 0) + abs(rcnt+gcnt+ycnt-(rv[rcnt]+val1))); if(gcnt+1 < g) ret = min(ret, go(rcnt, gcnt+1, ycnt, 1) + abs(rcnt+gcnt+ycnt-(gv[gcnt]+val2))); } return ret; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; string s; cin >> n >> s; for(int i = 0; i < n; i++) { if(s[i] == 'R') { r++; rv.push_back(i); } else if(s[i] == 'G') { g++; gv.push_back(i); } else { y++; yv.push_back(i); } } for(int i = 0; i <= r; i++) for(int j = 0; j <= g; j++) for(int k = 0; k <= y; k++) dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = -1; int ans = min(go(0, 0, 0, 0), min(go(0, 0, 0, 1), go(0, 0, 0, 2))); if(ans == INF) cout << "-1\n"; else cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...