#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 407;
constexpr int oo = 1e9;
int sumpref[MAXN][3];
int POS[MAXN][MAXN][MAXN][3];
int dp[MAXN][MAXN][MAXN][3];
vector<int> idx[3];
int R,G,Y;
int n;
int check(int i, int j, int k, int v){
int ith, sum = 0;
if(v == 0)
ith = idx[v][i-1];
if(v == 1)
ith = idx[v][j-1];
if(v == 2)
ith = idx[v][k-1];
sum += max(sumpref[ith][0], i);
sum += max(sumpref[ith][1], j);
sum += max(sumpref[ith][2], k);
return sum;
}
void computePos(){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
for(int k = 1; k <= n; k++){
if(k <= R && i <= G && j <= Y)
POS[k][i][j][0] = check(k, i, j, 0);
if(i <= R && k <= G && j <= Y)
POS[i][k][j][1] = check(i, k, j, 1);
if(i <= R && j <= G && k <= Y)
POS[i][j][k][2] = check(i, j, k, 2);
}
}
}
}
void solve(){
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
for(int k = 0; k <= n; k++)
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = oo;
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
//dp[i][j][k][v]
// i -> pozycja
// j -> ile R
// k -> ile G
for(int i = 1; i <= n; i++){
for(int j = 0; j <= R; j++){
for(int k = 0; k <= G; k++){
//dla 0 -> {1, 2}
//dla 1 -> {0, 2}
//dla 2 -> {1, 2}
//na pozycji itej stawiamy R
if(j)
dp[i][j][k][0] = min(dp[i-1][j-1][k][1], dp[i-1][j-1][k][2]) + abs(i - POS[j][k][i - (j+k)][0]);
//na pozycji itej stawiamy G
if(k)
dp[i][j][k][1] = min(dp[i-1][j][k-1][0], dp[i-1][j][k-1][2]) + abs(i - POS[j][k][i - (j+k)][1]);
//na pozycji itej stawiamy Y
if(i - (j+k) && i - (j+k) <= Y)
dp[i][j][k][2] = min(dp[i-1][j][k][0], dp[i-1][j][k][1]) + abs(i - POS[j][k][i - (j+k)][2]);
}
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
char c;
cin >> c;
if(c == 'R'){
idx[0].push_back(i);
R++;
}
else if(c == 'G'){
idx[1].push_back(i);
G++;
}
else{
idx[2].push_back(i);
Y++;
}
sumpref[i][0] = R;
sumpref[i][1] = G;
sumpref[i][2] = Y;
}
computePos();
solve();
int res = min({dp[n][R][G][0], dp[n][R][G][1], dp[n][R][G][2]});
if(res == oo) cout << "-1 \n";
else cout << res << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
3 ms |
29144 KB |
Output is correct |
| 5 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45524 KB |
Output is correct |
| 7 |
Correct |
5 ms |
47704 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 9 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 10 |
Correct |
7 ms |
53852 KB |
Output is correct |
| 11 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
4 ms |
43612 KB |
Output is correct |
| 13 |
Incorrect |
4 ms |
39516 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
3 ms |
29144 KB |
Output is correct |
| 5 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45524 KB |
Output is correct |
| 7 |
Correct |
5 ms |
47704 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 9 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 10 |
Correct |
7 ms |
53852 KB |
Output is correct |
| 11 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
4 ms |
43612 KB |
Output is correct |
| 13 |
Incorrect |
4 ms |
39516 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12888 KB |
Output is correct |
| 2 |
Runtime error |
466 ms |
1048576 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
3 ms |
29144 KB |
Output is correct |
| 5 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 6 |
Correct |
5 ms |
45524 KB |
Output is correct |
| 7 |
Correct |
5 ms |
47704 KB |
Output is correct |
| 8 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 9 |
Correct |
5 ms |
45660 KB |
Output is correct |
| 10 |
Correct |
7 ms |
53852 KB |
Output is correct |
| 11 |
Correct |
5 ms |
43612 KB |
Output is correct |
| 12 |
Correct |
4 ms |
43612 KB |
Output is correct |
| 13 |
Incorrect |
4 ms |
39516 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
