#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string S;
cin >> S;
vector<int> a(n);
array<int, 3> cnt{};
vector<vector<int>> g(3);
for (int i = 0; i < n; ++i) {
a[i] = S[i] == 'R' ? 0 : S[i] == 'G' ? 1 : 2;
++cnt[a[i]];
g[a[i]].push_back(i);
}
if (max({cnt[0], cnt[1], cnt[2]}) > (n + 1) / 2) {
cout << -1;
return 0;
}
array<int, 3> pl[cnt[0] + 1][cnt[1] + 1][cnt[2] + 1];
int dp[3][cnt[0] + 1][cnt[1] + 1][cnt[2] + 1];
pl[0][0][0] = {-1, -1, -1};
for (int t = 0; t < 3; ++t) {
reverse(g[t].begin(), g[t].end());
dp[t][0][0][0] = 0;
}
for (int sum = 1; sum <= n; ++sum) {
for (int f = 0; f <= cnt[0]; ++f) {
for (int s = 0; s <= cnt[1]; ++s) {
if (f + s > sum || sum - f - s > cnt[2]) {
break;
}
int t = sum - f - s;
if (t > cnt[2]) {
continue;
}
array<int, 3> temp = {f == 0 ? n + 1 : g[0][f - 1], s == 0 ? n + 1 : g[1][s - 1],
t == 0 ? n + 1 : g[2][t - 1]};
int idx = min_element(temp.begin(), temp.end()) - temp.begin();
if (idx == 0) {
pl[f][s][t] = pl[f - 1][s][t];
} else if (idx == 1) {
pl[f][s][t] = pl[f][s - 1][t];
} else {
pl[f][s][t] = pl[f][s][t - 1];
}
for (int k = 0; k < 3; ++k) if (pl[f][s][t][k] != -1) pl[f][s][t][k] += 1;
pl[f][s][t][idx] = 0;
array<int, 3> num = {f, s, t};
if (sum != n) {
for (int p = 0; p < 3; ++p) {
dp[p][f][s][t] = 1000'000'000;
for (int nxt = 0; nxt < 3; ++nxt) {
if (p == nxt || num[nxt] == 0) {
continue;
}
int ans = dp[nxt][f - (nxt == 0)][s - (nxt == 1)][t - (nxt == 2)] + pl[f][s][t][nxt];
if (dp[p][f][s][t] > ans) {
dp[p][f][s][t] = ans;
}
}
}
}
}
}
}
int ans = 1000'000'000;
int f = cnt[0], s = cnt[1], t = cnt[2];
array<int, 3> k = pl[f][s][t];
for (int nxt = 0; nxt < 3; ++nxt) {
if (cnt[nxt] == 0) {
continue;
}
int val = dp[nxt][f - (nxt == 0)][s - (nxt == 1)][t - (nxt == 2)] + pl[f][s][t][nxt];
ans = min(ans, val);
}
cout << ans;
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:73:19: warning: variable 'k' set but not used [-Wunused-but-set-variable]
73 | array<int, 3> k = pl[f][s][t];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
