oj.uz

Submission #952713

# Submission time Handle Problem Language Result Execution time Memory
952713 2024-03-24T16:03:59 Z NourWael Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 453 ms 1040724 KB 
#include <bits/stdc++.h>
using namespace std; 
int const mxN = 405;
int n;
int dp[mxN][mxN][mxN][4], 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; }
  }
  int 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 453 ms 1040280 KB Output is correct
2 Correct 302 ms 1040548 KB Output is correct
3 Correct 299 ms 1040248 KB Output is correct
4 Correct 301 ms 1040420 KB Output is correct
5 Correct 319 ms 1040276 KB Output is correct
6 Correct 309 ms 1040212 KB Output is correct
7 Correct 296 ms 1040248 KB Output is correct
8 Correct 311 ms 1040436 KB Output is correct
9 Correct 299 ms 1040432 KB Output is correct
10 Incorrect 295 ms 1040280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1040280 KB Output is correct
2 Correct 302 ms 1040548 KB Output is correct
3 Correct 299 ms 1040248 KB Output is correct
4 Correct 301 ms 1040420 KB Output is correct
5 Correct 319 ms 1040276 KB Output is correct
6 Correct 309 ms 1040212 KB Output is correct
7 Correct 296 ms 1040248 KB Output is correct
8 Correct 311 ms 1040436 KB Output is correct
9 Correct 299 ms 1040432 KB Output is correct
10 Incorrect 295 ms 1040280 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 318 ms 1040360 KB Output is correct
2 Correct 297 ms 1040464 KB Output is correct
3 Correct 299 ms 1040328 KB Output is correct
4 Correct 291 ms 1040396 KB Output is correct
5 Correct 294 ms 1040464 KB Output is correct
6 Correct 291 ms 1040336 KB Output is correct
7 Correct 293 ms 1040272 KB Output is correct
8 Correct 292 ms 1040460 KB Output is correct
9 Correct 288 ms 1040412 KB Output is correct
10 Correct 298 ms 1040724 KB Output is correct
11 Correct 289 ms 1040444 KB Output is correct
12 Correct 295 ms 1040296 KB Output is correct
13 Correct 289 ms 1040468 KB Output is correct
14 Correct 300 ms 1040464 KB Output is correct
15 Correct 288 ms 1040392 KB Output is correct
16 Correct 292 ms 1040424 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 1040280 KB Output is correct
2 Correct 302 ms 1040548 KB Output is correct
3 Correct 299 ms 1040248 KB Output is correct
4 Correct 301 ms 1040420 KB Output is correct
5 Correct 319 ms 1040276 KB Output is correct
6 Correct 309 ms 1040212 KB Output is correct
7 Correct 296 ms 1040248 KB Output is correct
8 Correct 311 ms 1040436 KB Output is correct
9 Correct 299 ms 1040432 KB Output is correct
10 Incorrect 295 ms 1040280 KB Output isn't correct
11 Halted 0 ms 0 KB -