#include<bits/stdc++.h>
using namespace std;
const int N = 405;
int n, id[200], cnt[3][N], pos[3][N], iC[3], f[3][N][N][N], nmbr[3];
char c[N];
void update (int &_a, int _b) {
if (_a == -1 || _a > _b) _a = _b;
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.INP", "r", stdin);
id['R'] = 0;
id['G'] = 1;
id['Y'] = 2;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
++nmbr[ id[ c[i] ] ];
}
for (int i = 1; i <= n; ++i) {
cnt[0][i] = cnt[0][i - 1];
cnt[1][i] = cnt[1][i - 1];
cnt[2][i] = cnt[2][i - 1];
++cnt[ id[ c[i] ] ][i];
}
for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;
memset(f, -1, sizeof f);
f[0][0][0][0] = f[1][0][0][0] = f[2][0][0][0] = 0;
for (int ijk = 0; ijk <= n; ++ijk) {
for (int i = 0; i <= ijk; ++i) {
for (int j = 0; i + j <= ijk; ++j) {
int k = ijk - i - j;
if (f[0][i][j][k] != -1) {
if (j < nmbr[1]) update (f[1][i][j + 1][k], f[0][i][j][k] + max(0, cnt[0][ pos[1][j + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[2][ pos[1][j + 1] ] - cnt[2][ pos[2][k] ]) );
if (k < nmbr[2]) update (f[2][i][j][k + 1], f[0][i][j][k] + max(0, cnt[0][ pos[2][k + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[1][ pos[2][k + 1] ] - cnt[1][ pos[1][j] ]) );
}
if (f[1][i][j][k] != -1) {
if (i < nmbr[0]) update (f[0][i + 1][j][k], f[1][i][j][k] + max(0, cnt[1][ pos[0][i + 1] ] - cnt[1][ pos[1][j] ]) + max(0, cnt[2][ pos[0][i + 1] ] - cnt[2][ pos[2][k] ]) );
if (k < nmbr[2]) update (f[2][i][j][k + 1], f[1][i][j][k] + max(0, cnt[0][ pos[2][k + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[1][ pos[2][k + 1] ] - cnt[1][ pos[1][j] ]) );
}
if (f[2][i][j][k] != -1) {
if (i < nmbr[0]) update (f[0][i + 1][j][k], f[2][i][j][k] + max(0, cnt[1][ pos[0][i + 1] ] - cnt[1][ pos[1][j] ]) + max(0, cnt[2][ pos[0][i + 1] ] - cnt[2][ pos[2][k] ]) );
if (j < nmbr[1]) update (f[1][i][j + 1][k], f[2][i][j][k] + max(0, cnt[0][ pos[1][j + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[2][ pos[1][j + 1] ] - cnt[2][ pos[2][k] ]) );
}
}
}
}
int ans = -1;
if (f[0][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[0][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);
if (f[1][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[1][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);
if (f[2][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[2][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);
cout << ans;
return 0;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:23:26: warning: array subscript has type 'char' [-Wchar-subscripts]
++nmbr[ id[ c[i] ] ];
^
joi2019_ho_t3.cpp:30:25: warning: array subscript has type 'char' [-Wchar-subscripts]
++cnt[ id[ c[i] ] ][i];
^
joi2019_ho_t3.cpp:33:48: warning: array subscript has type 'char' [-Wchar-subscripts]
for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;
^
joi2019_ho_t3.cpp:33:68: warning: array subscript has type 'char' [-Wchar-subscripts]
for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
643 ms |
780408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
643 ms |
780408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
641 ms |
780432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
643 ms |
780408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
