/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 410, inf = 1e9;
int n, a[maxn], dp[maxn][maxn][maxn][3];
string s;
vector < int > pos[3];
pair < int, int > prf[3][maxn];
void solve()
{
cin >> n >> s;
for (int i = 0; i < n; i ++)
{
if (s[i] == 'R')
a[i + 1] = 0;
else if (s[i] == 'G')
a[i + 1] = 1;
else if (s[i] == 'Y')
a[i + 1] = 2;
}
for (int i = 1; i <= n; i ++)
pos[a[i]].push_back(i);
for (int i = 0; i <= pos[0].size(); i ++)
for (int j = 0; j <= pos[1].size(); j ++)
for (int k = 0; k <= pos[2].size(); k ++)
dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = inf;
dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
for (int i = 0; i < pos[0].size(); i ++)
{
int f1 = 0;
while(f1 < pos[1].size() && pos[0][i] > pos[1][f1])
f1 ++;
int f2 = 0;
while(f2 < pos[2].size() && pos[0][i] > pos[2][f2])
f2 ++;
///cout << i << " " << f1 << " " << f2 << endl;
prf[0][i] = {f1, f2};
}
for (int i = 0; i < pos[1].size(); i ++)
{
int f1 = 0;
while(f1 < pos[0].size() && pos[1][i] > pos[0][f1])
f1 ++;
int f2 = 0;
while(f2 < pos[2].size() && pos[1][i] > pos[2][f2])
f2 ++;
prf[1][i] = {f1, f2};
}
for (int i = 0; i < pos[2].size(); i ++)
{
int f1 = 0;
while(f1 < pos[0].size() && pos[2][i] > pos[0][f1])
f1 ++;
int f2 = 0;
while(f2 < pos[1].size() && pos[2][i] > pos[1][f2])
f2 ++;
prf[2][i] = {f1, f2};
}
for (int p = 0; p < n; p ++)
{
for (int i = 0; i <= min(p, (int)pos[0].size()); i ++)
for (int j = 0; j <= min(p - i, (int)(pos[1].size())); j ++)
{
int k = p - i - j;
if (k > pos[2].size())
continue;
///cout << i << " " << j << " " << k << " " << dp[i][j][k][0] << " " << dp[i][j][k][1] << " " << dp[i][j][k][2] << endl;
if (i < (int)pos[0].size())
{
int add0 = min(dp[i][j][k][1], dp[i][j][k][2]);
int sd = (pos[0][i] - (p + 1))
+ max(0, j - prf[0][i].first)
+ max(0, k - prf[0][i].second);
add0 = add0 + max(0, sd);
dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], add0);
}
if (j < (int)pos[1].size())
{
///cout << "here" << endl;
int add1 = min(dp[i][j][k][0], dp[i][j][k][2]);
int sd = (pos[1][j] - (p + 1))
+ max(0, i - prf[1][i].first)
+ max(0, k - prf[1][i].second);
/**for (int f = 0; f < i; f ++)
if (pos[0][f] > pos[1][j])
sd ++;
for (int f = 0; f < k; f ++)
if (pos[2][f] > pos[1][j])
sd ++;*/
add1 = add1 + max(0, sd);
dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], add1);
}
if (k < (int)pos[2].size())
{
int add2 = min(dp[i][j][k][0], dp[i][j][k][1]);
int sd = pos[2][k] - (p + 1)
+ max(0, i - prf[2][i].first)
+ max(0, j - prf[2][i].second);
/**for (int f = 0; f < i; f ++)
if (pos[0][f] > pos[2][k])
sd ++;
for (int f = 0; f < j; f ++)
if (pos[1][f] > pos[2][k])
sd ++;*/
add2 = add2 + max(0, sd);
dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], add2);
}
}
}
///cout << dp[1][1][0][1] << endl;
int ans = inf;
for (int last = 0; last < 3; last ++)
ans = min(ans, dp[pos[0].size()][pos[1].size()][pos[2].size()][last]);
if (ans >= inf)
cout << -1 << endl;
else
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
/**
15
YYYRRRRRGGGGGGG
*/
Compilation message
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i <= pos[0].size(); i ++)
| ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for (int j = 0; j <= pos[1].size(); j ++)
| ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int k = 0; k <= pos[2].size(); k ++)
| ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i = 0; i < pos[0].size(); i ++)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while(f1 < pos[1].size() && pos[0][i] > pos[1][f1])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while(f2 < pos[2].size() && pos[0][i] > pos[2][f2])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < pos[1].size(); i ++)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while(f1 < pos[0].size() && pos[1][i] > pos[0][f1])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | while(f2 < pos[2].size() && pos[1][i] > pos[2][f2])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < pos[2].size(); i ++)
| ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while(f1 < pos[0].size() && pos[2][i] > pos[0][f1])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while(f2 < pos[1].size() && pos[2][i] > pos[1][f2])
| ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | if (k > pos[2].size())
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
