Submission #483583

#	Time	Username	Problem	Language	Result	Execution time	Memory
483583		TLP39	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	198 ms	96436 KiB

joi2019_ho_t3

#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);
      |     ~~~~~^~~~~~~~

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