/**
GOT A FEELING THAT I"M GOING UNDER
**/
#include <bits/stdc++.h>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 405;
int dp[N][N][N][3], n, in[3][N], cnt[3], cn[3][2][N][N];
string s;
main(){
cin >> n >> s;
s = ' ' + s;
memset(dp, 0x3f3f3f3f, sizeof(dp) );
for (int i = 1; i <= n; i++) {
if (s[i] == 'R') {
cnt[0]++;
in[0][cnt[0]] = i;
}
else if (s[i] == 'G') {
cnt[1]++;
in[1][cnt[1]] = i;
}
else {
cnt[2]++;
in[2][cnt[2]] = i;
}
}
for (int i = 1; i <= cnt[0]; i++) {
for (int j = 1; j <= cnt[1]; j++) {
if ( in[1][j] > in[0][i] )
cn[0][0][i][j] = cn[0][0][i][j - 1] + 1;
}
for (int j = 1; j <= cnt[2]; j++) {
if ( in[2][j] > in[0][i] )
cn[0][1][i][j] = cn[0][1][i][j - 1] + 1;
}
}
for (int i = 1; i <= cnt[1]; i++) {
for (int j = 1; j <= cnt[0]; j++) {
if ( in[0][j] > in[1][i] )
cn[1][0][i][j] = cn[1][0][i][j - 1] + 1;
}
for (int j = 1; j <= cnt[2]; j++) {
if ( in[2][j] > in[1][i] )
cn[1][1][i][j] = cn[1][1][i][j - 1] + 1;
}
}
for (int i = 1; i <= cnt[2]; i++) {
for (int j = 1; j <= cnt[1]; j++) {
if ( in[1][j] > in[2][i] )
cn[2][0][i][j] = cn[2][0][i][j - 1] + 1;
}
for (int j = 1; j <= cnt[0]; j++) {
if ( in[0][j] > in[2][i] )
cn[2][1][i][j] = cn[2][1][i][j - 1] + 1;
}
}
dp[0][0][0][0] = 0;
dp[0][0][0][1] = 0;
dp[0][0][0][2] = 0;
for (int i = 0; i <= cnt[0]; i++) {
for (int j = 0; j <= cnt[1]; j++) {
for (int k = 0; k <= cnt[2]; k++) {
for (int last = 0; last < 3; last++) {
if (i + 1 <= cnt[0] && last != 0)
dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[0][i + 1] + cn[0][0][i + 1][j] + cn[0][1][i + 1][k]) ) );
if (j + 1 <= cnt[1] && last != 1)
dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[1][j + 1] + cn[1][0][j + 1][i] + cn[1][1][j + 1][k]) ) );
if (k + 1 <= cnt[2] && last != 2){
dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[2][k + 1] + cn[2][0][k + 1][j] + cn[2][1][k + 1][i]) ) );
}
}
}
}
}
//while (1) {
// int a, b, c, d;
// cin >> a >> b >> c >> d;
// cout << dp[a][b][c][d] << endl;
//}
if ( min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) > 1e9 )
cout << -1 << endl;
else
cout << min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) << endl;
}
Compilation message
joi2019_ho_t3.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
780248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
780248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
565 ms |
780408 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
780248 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
