#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
using namespace std;
const int N = 5e5+5;
ll n, m, k, x, y, a, b, t, q, ans, sum;
vector< ll > g_ind, r_ind, y_ind;
ll A[N],B[N];
char C[N];
int G,R,Y;
int g_num[N], r_num[N], y_num[N];
int ind;
int dp[405][405][405][4];
int calc(int x,int y){
if(x==-1 && y==-1)return -1;
if(x==-1)return y;
if(y==-1)return x;
return min(x,y);
}
main()
{
ios::sync_with_stdio(0);
g_ind.push_back(0);
r_ind.push_back(0);
y_ind.push_back(0);
cin >> n;
for(int i=1;i<=n;i++){
cin >> C[i];
g_num[i] = g_num[i-1];
r_num[i] = r_num[i-1];
y_num[i] = y_num[i-1];
if( C[i] == 'G' ){
g_ind.push_back(i);
G++;
g_num[i]++;
}
if( C[i] == 'R' ){
r_ind.push_back(i);
R++;
r_num[i]++;
}
if( C[i] == 'Y' ){
y_ind.push_back(i);
Y++;
y_num[i]++;
}
}
for(int g = 0; g <= G; g++ )
for(int r = 0; r <= R; r++ )
for(int y = 0; y <= Y; y++ )
for(int i=1;i<=3;i++)
dp[g][r][y][i]=-1;
for(int i=1;i<=3;i++)
dp[0][0][0][i]=0;
for(int g = 0; g <= G; g++ )
for(int r = 0; r <= R; r++ )
for(int y = 0; y <= Y; y++ ){
int sul = g+r+y;
sul++;
sul /= 2;
ind = g_ind[g];
if( g>0 && g<=sul ){
int z = calc( dp[g - 1][r][y][2] , dp[g - 1][r][y][3] );
if(z!=-1)
dp[g][r][y][1] = z + max(0,(r_num[ind] - r_num[r_ind[r]])) + max(0,(y_num[ind] - y_num[y_ind[y]]));
}
ind = r_ind[r];
if( r>0 && r<=sul ){
int z = calc( dp[g][r - 1][y][1] , dp[g][r - 1][y][3] );
if(z!=-1)
dp[g][r][y][2] = z + max(0,(g_num[ind] - g_num[g_ind[g]])) + max(0,(y_num[ind] - y_num[y_ind[y]]));
}
ind = y_ind[y];
if( y>0 && y<=sul ){
int z = calc( dp[g][r][y - 1][1] , dp[g][r][y - 1][2] );
if(z!=-1)
dp[g][r][y][3] = z + max(0,(g_num[ind] - g_num[g_ind[g]])) + max(0,(r_num[ind] - r_num[r_ind[r]]));
}
// cout << dp[g][r][y][1] <<" "<< dp[g][r][y][2] <<" "<< dp[g][r][y][3] << endl;
// cout<<g<<" "<<r<<" "<<y<<endl;
// cout<<endl;
}
cout << min( dp[G][R][Y][1] , min( dp[G][R][Y][2] , dp[G][R][Y][3] ) ) << endl;
}
Compilation message
joi2019_ho_t3.cpp:31:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
