#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout<<#x<<':'<<x<<endl;
const int mxn = 404;
const int inf = mxn*mxn*mxn;
int dp[2][mxn][mxn][3];
string s;
vector<int> pos[3];
int pref[mxn][3];
int calc(int sx,int sy,int sz,int ex,int ey,int ez){
return max(sx-ex,0)+max(sy-ey,0)+max(sz-ez,0);
}
int main(){
int n;
cin>>n>>s;
for(int i = 0;i<n;i++){
if(s[i] == 'R')pos[0].push_back(i);
else if(s[i] == 'G')pos[1].push_back(i);
else pos[2].push_back(i);
}
for(int i = 0;i<n;i++){
if(i != 0)for(int j = 0;j<3;j++)pref[i][j] = pref[i-1][j];
if(s[i] == 'R')pref[i][0]++;
else if(s[i] == 'G')pref[i][1]++;
else pref[i][2]++;
}
//for(int i = 0;i<n;i++)cout<<pref[i][0]<<' '<<pref[i][1]<<' '<<pref[i][2]<<endl;
bool roll = 0;
for(auto &i:dp)for(auto &j:i)for(auto &k:j)for(auto &kk:k)kk = inf;
if(pos[0].size()>0)dp[roll][1][0][0] = pos[0][0];
if(pos[1].size()>0)dp[roll][0][1][1] = pos[1][0];
if(pos[2].size()>0)dp[roll][0][0][2] = pos[2][0];
//for(int i = 0;i<3;i++){cout<<i<<":";for(auto &j:pos[i])cout<<j<<' ';cout<<endl;}
for(int i = 1;i<n;i++){
roll^=1;
for(int j = 0;j<=pos[0].size();j++){
for(int k = 0;k<=pos[1].size();k++){
int l = i+1-j-k;
fill(dp[roll][j][k],dp[roll][j][k]+3,inf);
if(l<0||l>pos[2].size())continue;
//cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
if(j>0)dp[roll][j][k][0] = min(dp[roll^1][j-1][k][1],dp[roll^1][j-1][k][2])+
calc(j,k,l,pref[pos[0][j-1]][0],pref[pos[0][j-1]][1],pref[pos[0][j-1]][2]);
if(k>0)dp[roll][j][k][1] = min(dp[roll^1][j][k-1][0],dp[roll^1][j][k-1][2])+
calc(j,k,l,pref[pos[1][k-1]][0],pref[pos[1][k-1]][1],pref[pos[1][k-1]][2]);
if(l>0)dp[roll][j][k][2] = min(dp[roll^1][j][k][1],dp[roll^1][j][k][0])+
calc(j,k,l,pref[pos[2][l-1]][0],pref[pos[2][l-1]][1],pref[pos[2][l-1]][2]);
}
}
}
for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
int ans = *min_element(dp[roll][pos[0].size()][pos[1].size()],dp[roll][pos[0].size()][pos[1].size()]+3);
if(ans>=inf)cout<<-1;
else cout<<ans;
}
Compilation message
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = 0;j<=pos[0].size();j++){
| ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int k = 0;k<=pos[1].size();k++){
| ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(l<0||l>pos[2].size())continue;
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
| ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0;i<pos[0].size();i++)for(int j = 0;j<pos[1].size();j++)assert(dp[roll][i][j][0]+dp[roll][i][j][1]+dp[roll][i][j][2] >= inf);
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4052 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4052 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4052 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4052 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4052 KB |
Output is correct |
| 2 |
Correct |
32 ms |
4124 KB |
Output is correct |
| 3 |
Correct |
30 ms |
4052 KB |
Output is correct |
| 4 |
Incorrect |
46 ms |
4020 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4052 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4052 KB |
Output is correct |
| 6 |
Incorrect |
3 ms |
4052 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
