oj.uz

Submission #952712

# Submission time Handle Problem Language Result Execution time Memory
952712 2024-03-24T16:01:42 Z NourWael Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1040296 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));
   //if(i==n-1) cout<<red<<' '<<yell<<' '<<green<<'\n';
   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 Execution timed out 1082 ms 954632 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 1082 ms 954632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 25.0

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