Submission #265421

#	Time	Username	Problem	Language	Result	Execution time	Memory
265421		MKopchev	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	64 ms	97276 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 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];

            ret=min(ret,abs(would-cnt_0-cnt_1-cnt_2-1)+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;
    }

    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)/2);
    return 0;
}

Compilation message (stderr)

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

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