Submission #220751

#TimeUsernameProblemLanguageResultExecution timeMemory
220751hanagasumiGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
15 / 100
7 ms944 KiB
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <deque> #include <map> #include <set> #include <complex> #include <string> #include <unordered_map> #include <unordered_set> #include <random> #define ft first #define sc second #define pb push_back #define len(v) (int)v.size() // #define int ll using namespace std; typedef long long ll; int inf = 1e9 + 100; signed main() { #ifdef PC freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; string s; cin >> s; for (int i = 0; i < len(s); i++) { if(s[i] == 'R') s[i] = 'a'; if(s[i] == 'G') s[i] = 'b'; if(s[i] == 'Y') s[i] = 'c'; } vector<int> a, b, c; for (int i = 0; i < len(s); i++) { if(s[i] == 'a') a.pb(i); if(s[i] == 'b') b.pb(i); if(s[i] == 'c') c.pb(i); } int maxa = len(a), maxb = len(b), maxc = len(c); // cout << maxa << " " << maxb << " " << maxc << endl; int dp[maxa + 1][maxb + 1][maxc + 1][3]; for (int i = 0; i <= maxa; i++) { for (int j = 0; j <= maxb; j++) { for (int z = 0; z <= maxc; z++) { for (int pr = 0; pr < 3; pr++) dp[i][j][z][pr] = inf; } } } dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0; for (int i = 0; i <= maxa; i++) { for (int j = 0; j <= maxb; j++) { for (int z = 0; z <= maxc; z++) { for (int pr = 0; pr < 3; pr++) { // cout << i << " " << j << " " << z << " " << pr << " " << dp[i][j][z][pr] << endl; int pos = i + j + z; for (char nxt = 'a'; nxt <= 'c'; nxt++) { if(nxt - 'a' == pr) continue; if(nxt == 'a' && i == maxa) continue; if(nxt == 'b' && j == maxb) continue; if(nxt == 'c' && z == maxc) continue; if(nxt == 'a') { dp[i + 1][j][z][0] = min(dp[i + 1][j][z][0], dp[i][j][z][pr] + max(0, pos - a[i])); } if(nxt == 'b') { dp[i][j + 1][z][1] = min(dp[i][j + 1][z][1], dp[i][j][z][pr] + max(0, pos - b[j])); } if(nxt == 'c') { dp[i][j][z + 1][2] = min(dp[i][j][z + 1][2], dp[i][j][z][pr] + max(0, pos - c[z])); } } } } } } int ans = min(dp[maxa][maxb][maxc][0], min(dp[maxa][maxb][maxc][1], dp[maxa][maxb][maxc][2])); if(ans == inf) ans = -1; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...