oj.uz

Submission #952720

# Submission time Handle Problem Language Result Execution time Memory
952720 2024-03-24T16:15:18 Z NourWael Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 1040492 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 = 2e9, 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==2e9? -1:fin);
   return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 532 ms 1040356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 532 ms 1040356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1040404 KB Output is correct
2 Correct 443 ms 1040468 KB Output is correct
3 Correct 331 ms 1040376 KB Output is correct
4 Correct 318 ms 1040360 KB Output is correct
5 Correct 298 ms 1040492 KB Output is correct
6 Correct 348 ms 1040352 KB Output is correct
7 Correct 284 ms 1040340 KB Output is correct
8 Correct 287 ms 1040244 KB Output is correct
9 Correct 290 ms 1040464 KB Output is correct
10 Correct 287 ms 1040396 KB Output is correct
11 Correct 289 ms 1040416 KB Output is correct
12 Correct 287 ms 1040464 KB Output is correct
13 Correct 283 ms 1040368 KB Output is correct
14 Correct 282 ms 1040396 KB Output is correct
15 Correct 284 ms 1040464 KB Output is correct
16 Correct 279 ms 1040352 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 532 ms 1040356 KB Time limit exceeded
2 Halted 0 ms 0 KB -