oj.uz

Submission #952724

# Submission time Handle Problem Language Result Execution time Memory
952724 2024-03-24T16:16:23 Z NourWael Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 319 ms 1040468 KB 
#include <bits/stdc++.h>
using namespace std; 
int const mxN = 405;
int n;
int dp[mxN][mxN][mxN][4];
int cnt[mxN][3], ind[mxN+5][3];

int solve ( int i, int red, int yell, int b ) {
   if(i==n) return 0;
   if(~dp[i][red][yell][b]) return dp[i][red][yell][b];

   int ans = 1e9, green = i-(red+yell), gn = ind[green+1][2], rn = ind[red+1][0], yn = ind[yell+1][1];

   if(b!=0 && red+1<=cnt[n][0]) ans = solve(i+1, red+1, yell, 0) + max(0, cnt[rn][2]-green) + max(0, cnt[rn][1]-yell);
   if(b!=1 && yell+1<=cnt[n][1]) ans = min (ans, solve(i+1, red, yell+1, 1) + max(0, cnt[yn][0]-red) + max(0, cnt[yn][2]-green));
   if(b!=2 && green+1<=cnt[n][2]) ans = min (ans, solve(i+1, red, yell, 2) + max(0, cnt[gn][0]-red) + max(0, cnt[gn][1]-yell));
 
   return dp[i][red][yell][b] = ans;
}
int main() {
  
  ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  cin>>n;
  string s; cin>>s;
  memset(dp,-1,sizeof dp);
  for(int i=1; i<=n; i++) {
    cnt[i][0] = cnt[i-1][0];
    cnt[i][1] = cnt[i-1][1];
    cnt[i][2] = cnt[i-1][2];
    if(s[i-1]=='R') { cnt[i][0]++; ind[cnt[i][0]][0] = i; }
    else if(s[i-1]=='Y') { cnt[i][1]++; ind[cnt[i][1]][1] = i;}
    else { cnt[i][2]++; ind[cnt[i][2]][2] = i; }
  }
  long long fin = solve(0,0,0,3);
  cout<<(fin==1e9? -1:fin);
   return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 1040248 KB Output is correct
2 Correct 286 ms 1040372 KB Output is correct
3 Correct 295 ms 1040248 KB Output is correct
4 Correct 315 ms 1040220 KB Output is correct
5 Correct 275 ms 1040240 KB Output is correct
6 Correct 291 ms 1040424 KB Output is correct
7 Correct 281 ms 1040212 KB Output is correct
8 Correct 276 ms 1040412 KB Output is correct
9 Correct 280 ms 1040468 KB Output is correct
10 Incorrect 319 ms 1040292 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 1040248 KB Output is correct
2 Correct 286 ms 1040372 KB Output is correct
3 Correct 295 ms 1040248 KB Output is correct
4 Correct 315 ms 1040220 KB Output is correct
5 Correct 275 ms 1040240 KB Output is correct
6 Correct 291 ms 1040424 KB Output is correct
7 Correct 281 ms 1040212 KB Output is correct
8 Correct 276 ms 1040412 KB Output is correct
9 Correct 280 ms 1040468 KB Output is correct
10 Incorrect 319 ms 1040292 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 1040220 KB Output is correct
2 Correct 287 ms 1040332 KB Output is correct
3 Correct 314 ms 1040464 KB Output is correct
4 Correct 279 ms 1040424 KB Output is correct
5 Correct 277 ms 1040276 KB Output is correct
6 Correct 277 ms 1040432 KB Output is correct
7 Correct 281 ms 1040424 KB Output is correct
8 Correct 277 ms 1040464 KB Output is correct
9 Correct 291 ms 1040376 KB Output is correct
10 Correct 285 ms 1040300 KB Output is correct
11 Correct 286 ms 1040332 KB Output is correct
12 Correct 274 ms 1040272 KB Output is correct
13 Correct 287 ms 1040300 KB Output is correct
14 Correct 293 ms 1040248 KB Output is correct
15 Correct 299 ms 1040268 KB Output is correct
16 Correct 288 ms 1040332 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 1040248 KB Output is correct
2 Correct 286 ms 1040372 KB Output is correct
3 Correct 295 ms 1040248 KB Output is correct
4 Correct 315 ms 1040220 KB Output is correct
5 Correct 275 ms 1040240 KB Output is correct
6 Correct 291 ms 1040424 KB Output is correct
7 Correct 281 ms 1040212 KB Output is correct
8 Correct 276 ms 1040412 KB Output is correct
9 Correct 280 ms 1040468 KB Output is correct
10 Incorrect 319 ms 1040292 KB Output isn't correct
11 Halted 0 ms 0 KB -