oj.uz

Submission #759738

# Submission time Handle Problem Language Result Execution time Memory
759738 2023-06-16T17:28:51 Z Sarpa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 811524 KB 
// Be nam KHODA
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

typedef pair<int, int> pii;

const int N = 400 + 10, inf = 1e9 + 10;

int n;
int a[N];
int dp[N][N][N][3];
int cnt[N][3];
int pd[N][N][3];

int main(){
  cin.tie(0), ios::sync_with_stdio(0);
  cin >> n;
  for(int i = 0; i < n; i++){
    char c;
    cin >> c;
    if(c == 'R')
      a[i] = 0;
    else if(c == 'G')
      a[i] = 1;
    else a[i] = 2;
  }
  
    
  for(int j = 0; j < 3; j++){
    int cn = 0;
    for(int i = 0; i < n; i++){
      if(a[i] == j){
        cn++;
        cnt[cn][j] = i; 
      }
    }
  }
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      for(int z = i; z <= j; z++)
        for(int d = 0; d < 3; d++)
          if(a[z] == d)
            pd[i][j][d]++;

  int z = count(a, a + n, 0);
  int t = count(a, a + n, 1);
  int tw = count(a, a + n, 2);
  
  memset(dp, 63, sizeof dp);
  dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  for(int i = 0; i <= z; i++)
    for(int j = 0; j <= t; j++)
      for(int z = 0; z <= tw; z++)
        for(int q = 0; q < 3; q++){
          int ar[3] = {i, j, z};
          if(ar[q] == 0 or i + j + z == 0){
            continue;
          }
          int mx = max({cnt[i][0], cnt[j][1], cnt[z][2]});
          int qq = a[mx];
          int op = 1 ^ 2 ^ q ^ qq;
          int cost = mx - cnt[ar[q]][q], want = max(0, ar[op] - pd[0][cnt[ar[q]][q]][op]);
          cost -= pd[cnt[ar[q]][q]][mx][op] - want + pd[cnt[ar[q]][q] + 1][mx][q];
          ar[q]--;
          if(q == qq) cost = 0;
          for(int qq = 0; qq < 3; qq++) if(qq != q){
            dp[i][j][z][q] = min(dp[i][j][z][q], dp[ar[0]][ar[1]][ar[2]][qq] + cost); 
          }
        }
  int ans = inf;
  for(int i = 0; i < 3; i++)
    ans = min(ans, dp[z][t][tw][i]);
  if(ans >= inf) ans = -1;
  cout << ans << endl;
  return 0;   
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 809500 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 1064 ms 809500 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 809556 KB Output is correct
2 Correct 338 ms 811524 KB Output is correct
3 Correct 277 ms 811340 KB Output is correct
4 Correct 290 ms 811324 KB Output is correct
5 Correct 291 ms 811440 KB Output is correct
6 Correct 282 ms 811448 KB Output is correct
7 Correct 314 ms 811388 KB Output is correct
8 Correct 275 ms 811368 KB Output is correct
9 Correct 286 ms 811344 KB Output is correct
10 Correct 276 ms 811400 KB Output is correct
11 Correct 287 ms 811448 KB Output is correct
12 Correct 253 ms 810396 KB Output is correct
13 Correct 276 ms 810804 KB Output is correct
14 Correct 276 ms 811012 KB Output is correct
15 Correct 278 ms 811336 KB Output is correct
16 Correct 302 ms 811432 KB Output is correct

Subtask #4
0 / 25.0

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