Submission #759740

#	Time	Username	Problem	Language	Result	Execution time	Memory
759740		Sarpa	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	252 ms	136572 KiB

joi2019_ho_t3

// 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 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 = i; 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);
  
  vector<vector<vector<vector<int>>>> dp(z + 1, vector<vector<vector<int>>>(t + 1, vector<vector<int>>(tw + 1, vector<int>(4, inf))));

  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: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25