Submission #291568

#TimeUsernameProblemLanguageResultExecution timeMemory
291568reymontada61Growing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
151 ms189944 KiB
#include <bits/stdc++.h> using namespace std; int n; string s; int r, g, b; const int MXN = 405; int dp[MXN][MXN][MXN][4]; vector<int> rs, gs, bs; int pfr[MXN]; int pfg[MXN]; int pfb[MXN]; signed main() { cin >> n >> s; int rc = 0, bc = 0, gc = 0; for (int i=0; i<n; i++) { if (s[i] == 'R') { rs.push_back(i+1); r++; rc++; } if (s[i] == 'G') { gs.push_back(i+1); g++; gc++; } if (s[i] == 'Y') { bs.push_back(i+1); b++; bc++; } pfr[i+1] = r; pfg[i+1] = g; pfb[i+1] = b; } s = ' ' + s; for (int ind=1; ind<=n; ind++) { for (int r=0; r<=rc; r++) { for (int g=0; g<=gc; g++) { int b = ind - r - g; if (b >= 0 && b <= bc) { for (int whi=1; whi<=3; whi++) { int re = INT_MAX / 2; if (whi != 1 && r > 0) { int h = dp[ind-1][r-1][g][1]; int l = rs[r-1]; h += max(l + max(g - pfg[l], 0) + max(b - pfb[l], 0) - ind, 0); re = min(re, h); } if (whi != 2 && g > 0) { int h = dp[ind-1][r][g-1][2]; int l = gs[g-1]; h += max(l + max(b - pfb[l], 0) + max(r - pfr[l], 0) - ind, 0); re = min(re, h); } if (whi != 3 && b > 0) { int h = dp[ind-1][r][g][3]; int l = bs[b-1]; h += max(l + max(g - pfg[l], 0) + max(r - pfr[l], 0) - ind, 0); re = min(re, h); } dp[ind][r][g][whi] = re; } } } } } int re = dp[n][r][g][1]; for (int i=1; i<=3; i++) re = min(re, dp[n][r][g][i]); if (re > n * n * 2) { cout << -1 << endl; } else { cout << re << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...