Submission #483583

#TimeUsernameProblemLanguageResultExecution timeMemory
483583TLP39Growing Vegetable is Fun 3 (JOI19_ho_t3)C++14
100 / 100
198 ms96436 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...