This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
const int maxn = 401;
int posa[maxn];
int posb[maxn];
int posc[maxn];
vector<int> a, b, c;
int maxa = 0, maxb = 0, maxc = 0;
int cost(int a1, int b1, int c1, int num) {
int pos = 0;
if(num == 0)
pos = a[a1];
if(num == 1)
pos = b[b1];
if(num == 2)
pos = c[c1];
int pos1 = pos;
pos += max(0, posa[pos1] - (maxa - a1));
pos += max(0, posb[pos1] - (maxb - b1));
pos += max(0, posc[pos1] - (maxc - c1));
// cout << a1 << " " << b1 << " " << c1 << " " << (pos - (a1 + b1 + c1)) << " " << pos1 << " " << maxc << " " << posc[pos1] << endl;
return pos - (a1 + b1 + c1);
}
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';
posa[i] = posb[i] = posc[i] = 0;
}
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);
}
for (int i = len(s) - 1; i >= 0; i--) {
posa[i] = posa[i + 1];
posb[i] = posb[i + 1];
posc[i] = posc[i + 1];
if(s[i] == 'a')
posa[i]++;
if(s[i] == 'b')
posb[i]++;
if(s[i] == 'c')
posc[i]++;
}
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;
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] + cost(i, j, z, 0));
}
if(nxt == 'b') {
dp[i][j + 1][z][1] = min(dp[i][j + 1][z][1], dp[i][j][z][pr] + cost(i, j, z, 1));
}
if(nxt == 'c') {
dp[i][j][z + 1][2] = min(dp[i][j][z + 1][2], dp[i][j][z][pr] + cost(i, j, z, 2));
}
}
}
}
}
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |