Submission #547982

#	Time	Username	Problem	Language	Result	Execution time	Memory
547982		krit3379	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	92 ms	162960 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define N 405

int dp[N][N][N][3],sz[3],qs[3][N],ans;
char s[N];
vector<int> pos[3];

int main(){
    int n,i,j,k,l,idx,x;
    scanf("%d %s",&n,s+1);
    for(i=1;i<=n;i++){
        idx=(s[i]=='R')?0:(s[i]=='G')?1:2;
        pos[idx].push_back(i);
        qs[idx][i]++;
        sz[idx]++;
        for(j=0;j<3;j++)qs[j][i]+=qs[j][i-1];
    }
    for(i=0;i<=sz[0];i++)for(j=0;j<=sz[1];j++)for(k=0;k<=sz[2];k++)for(l=0;l<3;l++)dp[i][j][k][l]=1e9;
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    for(i=0;i<=sz[0];i++)for(j=0;j<=sz[1];j++)for(k=0;k<=sz[2];k++)for(l=0;l<3;l++){
        if(!i&&!j&&!k)continue;
        if(i&&l==0){
            idx=pos[0][i-1];
            x=idx-min(qs[0][idx],i)-min(qs[1][idx],j)-min(qs[2][idx],k);
            dp[i][j][k][l]=min(dp[i-1][j][k][1],dp[i-1][j][k][2])+x;
        }
        if(j&&l==1){
            idx=pos[1][j-1];
            x=idx-min(qs[0][idx],i)-min(qs[1][idx],j)-min(qs[2][idx],k);
            dp[i][j][k][l]=min(dp[i][j-1][k][0],dp[i][j-1][k][2])+x;
        }
        if(k&&l==2){
            idx=pos[2][k-1];
            x=idx-min(qs[0][idx],i)-min(qs[1][idx],j)-min(qs[2][idx],k);
            dp[i][j][k][l]=min(dp[i][j][k-1][0],dp[i][j][k-1][1])+x;
        }
    }
    ans=min({dp[sz[0]][sz[1]][sz[2]][0],dp[sz[0]][sz[1]][sz[2]][1],dp[sz[0]][sz[1]][sz[2]][2]});
    if(ans>=1e9)printf("-1");
    else printf("%d",ans);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d %s",&n,s+1);
      |     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25