Submission #265428

#	Time	Username	Problem	Language	Result	Execution time	Memory
265428		MKopchev	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	328 ms	97272 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
const int nmax=400+5;

int n;
int inp[nmax];

int where[3][nmax],pointer[3];

int dp[3][nmax/2][nmax/2][nmax/2];

int cnt[3][nmax];

int rec(int prv,int cnt_0,int cnt_1,int cnt_2)
{
    //cout<<prv<<" "<<cnt_0<<" "<<cnt_1<<" "<<cnt_2<<endl;

    if(cnt_0==pointer[0]&&cnt_1==pointer[1]&&cnt_2==pointer[2])return 0;

    if(prv!=-1&&dp[prv][cnt_0][cnt_1][cnt_2]!=-1)return dp[prv][cnt_0][cnt_1][cnt_2];

    int seen[3]={cnt_0,cnt_1,cnt_2};

    int ret=1e9;

    for(int cur=0;cur<3;cur++)
        if(cur!=prv&&seen[cur]<pointer[cur])
        {
            int would=where[cur][seen[cur]+1],should=cnt_0+cnt_1+cnt_2+1;

            int add=0;

            for(int t=0;t<3;t++)
                if(t!=cur)
                    add=add+max(0,seen[t]-cnt[t][would]);

            //cout<<cnt_0<<" "<<cnt_1<<" "<<cnt_2<<" "<<would<<" "<<add<<" "<<should<<endl;

            ret=min(ret,abs(would+add-should)+rec(cur,cnt_0+(cur==0),cnt_1+(cur==1),cnt_2+(cur==2)));
        }
    if(prv!=-1)dp[prv][cnt_0][cnt_1][cnt_2]=ret;
    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
    {
        char c=getchar();
        while(c!='R'&&c!='G'&&c!='Y')c=getchar();

        if(c=='R')inp[i]=0;
        if(c=='G')inp[i]=1;
        if(c=='Y')inp[i]=2;

        pointer[inp[i]]++;
        where[inp[i]][pointer[inp[i]]]=i;

        cnt[0][i]=cnt[0][i-1]+(inp[i]==0);
        cnt[1][i]=cnt[1][i-1]+(inp[i]==1);
        cnt[2][i]=cnt[2][i-1]+(inp[i]==2);
    }

    int MX=(n+1)/2;
    if(pointer[0]>MX||pointer[1]>MX||pointer[2]>MX)
    {
        printf("-1\n");
        return 0;
    }

    printf("%i\n",rec(-1,0,0,0));
    return 0;
}

Compilation message (stderr)

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

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