Submission #121336

#TimeUsernameProblemLanguageResultExecution timeMemory
121336onjo0127Growing Vegetable is Fun 3 (JOI19_ho_t3)C++11
100 / 100
195 ms163164 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; char S[409], C[4] = "RGY"; vector<int> T[3]; int P[3][409], D[409][409][409][3]; inline int its(int cn, int cc, int id) { return max(0, cc - P[cn][id]); } int go(int r, int g, int y, int x) { if(r+g+y == 0) return 0; int &ret = D[r][g][y][x]; if(ret != -1) return ret; ret = INF; if(r && x == 0) ret = min(ret, min(go(r-1, g, y, 1), go(r-1, g, y, 2)) + its(1, g, T[0][r-1]) + its(2, y, T[0][r-1])); if(g && x == 1) ret = min(ret, min(go(r, g-1, y, 0), go(r, g-1, y, 2)) + its(0, r, T[1][g-1]) + its(2, y, T[1][g-1])); if(y && x == 2) ret = min(ret, min(go(r, g, y-1, 0), go(r, g, y-1, 1)) + its(0, r, T[2][y-1]) + its(1, g, T[2][y-1])); return ret; } int main() { int N; scanf("%d",&N); for(int i=1; i<=N; i++) { scanf(" %c",&S[i]); for(int j=0; j<3; j++) if(S[i] == C[j]) T[j].push_back(i); } for(int i=1; i<=N; i++) for(int j=0; j<3; j++) P[j][i] = P[j][i-1] + (S[i] == C[j]); for(int i=0; i<=P[0][N]; i++) for(int j=0; j<=P[1][N]; j++) for(int k=0; k<=P[2][N]; k++) for(int l=0; l<3; l++) D[i][j][k][l] = -1; int ans = INF; for(int i=0; i<3; i++) if(P[i][N]) ans = min(ans, go(P[0][N], P[1][N], P[2][N], i)); if(ans == INF) puts("-1"); else printf("%d", ans); return 0; }

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d",&N);
         ~~~~~^~~~~~~~~
joi2019_ho_t3.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&S[i]);
   ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...