oj.uz

Submission #952716

# Submission time Handle Problem Language Result Execution time Memory
952716 2024-03-24T16:11:44 Z NourWael Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 379 ms 1048580 KB 
#include <bits/stdc++.h>
using namespace std; 
int const mxN = 405;
int n;
long long 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 = 1e18, 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==1e18? -1:fin);
   return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int solve(int, int, int, int)':
joi2019_ho_t3.cpp:12:14: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 |    int ans = 1e18, green = i-(red+yell), gn = ind[green+1][2], rn = ind[red+1][0], yn = ind[yell+1][1];
      |              ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 349 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 379 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -