Submission #890451

#TimeUsernameProblemLanguageResultExecution timeMemory
890451ParsaSGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++17
100 / 100
103 ms424784 KiB
// In the name of God #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define mp make_pair typedef long long ll; const int N = 400 + 5; int n; string s; int dp[N][N][N][3], cnt[N][3]; vector<int> vec[3]; void solve() { cin >> n >> s; for (int i = 0; i < n; i++) { for (int j = 0; j < 3 && i; j++) cnt[i][j] = cnt[i - 1][j]; if (s[i] == 'R') { cnt[i][0]++; vec[0].pb(i); } else if (s[i] == 'G') { cnt[i][1]++; vec[1].pb(i); } else { cnt[i][2]++; vec[2].pb(i); } } for (int r = 0; r <= cnt[n - 1][0]; r++) { for (int g = 0; g <= cnt[n - 1][1]; g++) { for (int y = 0; y <= cnt[n - 1][2]; y++) { for (int i = 0; i < 3; i++) { dp[r][g][y][i] = 1e9; if ((i == 0 && r == 0) || (i == 1 && g == 0) || (i == 2 && y == 0)) { if (r == 0 && g == 0 && y == 0) dp[r][g][y][i] = 0; continue; } int r2 = r - (i == 0), g2 = g - (i == 1), y2 = y - (i == 2); int k = vec[i][(i == 0 ? r : (i == 1 ? g : y)) - 1]; int d = (i != 0) * max(0, cnt[k][0] - r) + (i != 1) * max(0, cnt[k][1] - g) + (i != 2) * max(0, cnt[k][2] - y); for (int j = 0; j < 3; j++) { if (i == j) continue; dp[r][g][y][i] = min(dp[r][g][y][i], dp[r2][g2][y2][j] + d); } } } } } int ans = 1e9; for (int i = 0; i < 3; i++) ans = min(ans, dp[cnt[n - 1][0]][cnt[n - 1][1]][cnt[n - 1][2]][i]); cout << (ans < 1e9 ? ans : -1) << endl; } int32_t main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int tc = 1; // cin >> tc; while (tc--) { solve(); } 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...