This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int l;
char s[402];
int nR=0,nG=0,nY=0;
int pos[3][402];
int acc[402][3];
void init()
{
scanf("%d ",&l);
scanf("%s",s);
acc[0][0]=acc[0][1]=acc[0][2]=0;
for(int i=0;i<l;i++)
{
if(i)
{
acc[i][0]=acc[i-1][0];
acc[i][1]=acc[i-1][1];
acc[i][2]=acc[i-1][2];
}
if(s[i]=='R')
{
pos[0][nR]=i;
acc[i][0]++;
nR++;
}
else if(s[i]=='G')
{
pos[1][nG]=i;
acc[i][1]++;
nG++;
}
else
{
pos[2][nY]=i;
acc[i][2]++;
nY++;
}
}
}
int dp[202][202][202][3];
int MAX_INT = 1900000000;
int solve(int arr[],int typ)
{
if(dp[arr[0]][arr[1]][arr[2]][typ]>=0) return dp[arr[0]][arr[1]][arr[2]][typ];
int arr_copy[3]={arr[0],arr[1],arr[2]};
if(arr_copy[typ]==0) return dp[arr[0]][arr[1]][arr[2]][typ] = MAX_INT;
arr_copy[typ]--;
int carry = 0;
for(int i=0;i<3;i++)
{
if(i==typ) continue;
carry += max(0,arr_copy[i]-acc[pos[typ][arr_copy[typ]]][i]);
}
int dpBefore = MAX_INT;
for(int i=0;i<3;i++)
{
if(i==typ) continue;
dpBefore = min(dpBefore,solve(arr_copy,i));
}
return dp[arr[0]][arr[1]][arr[2]][typ] = dpBefore+carry;
}
int main()
{
init();
if(max(nR,max(nG,nY)) > (l+1)/2)
{
printf("-1");
return 0;
}
for(int i1=0;i1<=nR;i1++)
{
for(int i2=0;i2<=nG;i2++)
{
for(int i3=0;i3<=nY;i3++)
{
dp[i1][i2][i3][0]=dp[i1][i2][i3][1]=dp[i1][i2][i3][2]=-1;
}
}
}
dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
for(int i1=0;i1<=nR;i1++)
{
for(int i2=0;i2<=nG;i2++)
{
for(int i3=0;i3<=nY;i3++)
{
int arr[3] = {i1,i2,i3};
solve(arr,0);
solve(arr,1);
solve(arr,2);
}
}
}
printf("%d",min(dp[nR][nG][nY][0],min(dp[nR][nG][nY][1],dp[nR][nG][nY][2])));
}
Compilation message (stderr)
joi2019_ho_t3.cpp: In function 'void init()':
joi2019_ho_t3.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | scanf("%d ",&l);
| ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | scanf("%s",s);
| ~~~~~^~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |