/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 402;
int pr[3][N], n, dp[N][N][N][3],val[N][N][N][3];
vector<int> pos[3];
string s;
int ind(char x)
{
if (x == 'R')
return 0;
if (x == 'G')
return 1;
return 2;
}
int get(int i, int l, int r)
{
return max(0, pr[i][r] - pr[i][l - 1]);
}
void calc(int x,int a, int b, int c)
{
a++;
b++;
c++;
int p;
if (x == 0)
p = a;
else if (x == 1)
p = b;
else
p = c;
int res = 0;
if (p > pos[x].size())
{
val[a - 1][b - 1][c - 1][x] = mod;
return;
}
if (x != 0 && a <= pos[0].size())
res += get(0, pos[0][a - 1], pos[x][p - 1]);
if (x != 1 && b <= pos[1].size())
res += get(1, pos[1][b - 1], pos[x][p - 1]);
if (x != 2 && c <= pos[2].size())
res += get(2, pos[2][c - 1], pos[x][p - 1]);
val[a - 1][b - 1][c - 1][x] = res;
}
int main()
{
fastIO;
cin >> n;
cin >> s;
s = "#" + s;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 3; j++)
pr[j][i] = pr[j][i - 1];
pr[ind(s[i])][i]++;
pos[ind(s[i])].push_back(i);
}
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k <= n; k++)
{
calc(i, j, k, 0);
calc(i, j, k, 1);
calc(i, j, k, 2);
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = mod;
}
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
for (int k = 0; k < n; k++)
for (int a = 0; a <= k && a <= pos[0].size(); a++)
for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
{
int c = k - a - b;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
if (i == j)
continue;
dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j] = min(dp[a][b][c][i] + val[a][b][c][j], dp[a + (j == 0)][b + (j == 1)][c + (j == 2)][j]);
}
}
int ans = min(dp[pr[0][n]][pr[1][n]][pr[2][n]][0], min(dp[pr[0][n]][pr[1][n]][pr[2][n]][1], dp[pr[0][n]][pr[1][n]][pr[2][n]][2]));
if (ans == mod)
ans = -1;
cout << ans << endl;
return 0;
}
/*
*/
Compilation message
joi2019_ho_t3.cpp: In function 'void calc(int, int, int, int)':
joi2019_ho_t3.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p > pos[x].size())
~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x != 0 && a <= pos[0].size())
~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:70:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x != 1 && b <= pos[1].size())
~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x != 2 && c <= pos[2].size())
~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:104:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int a = 0; a <= k && a <= pos[0].size(); a++)
~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:105:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int b = 0; a + b <= k && b <= pos[1].size(); b++)
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
1680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
1680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Runtime error |
963 ms |
1048576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
512 KB |
Output is correct |
| 4 |
Runtime error |
38 ms |
1680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
