Submission #1066635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066635		fryingduc	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	86 ms	166228 KiB

joi2019_ho_t3

#include "bits/stdc++.h"
using namespace std;

const int maxn = 405;
int n, a[maxn];
string s;
int pref[maxn][3];
long long f[maxn][maxn][maxn][3];
vector<int> pos[maxn];

int convert(char c) {
  if(c == 'R') return 0;
  if(c == 'G') return 1;
  if(c == 'Y') return 2;
  
  return -1;
}
void solve() {
  cin >> n >> s;
  s = ' ' + s;
  for(int i = 1; i <= n; ++i) {
    a[i] = convert(s[i]);
    for(int j = 0; j < 3; ++j) {
      pref[i][j] = pref[i - 1][j];
    }
    pref[i][a[i]]++;
    pos[a[i]].push_back(i);
  }
  for(int i = 0; i <= pref[n][0]; ++i) {
    for(int j = 0; j <= pref[n][1]; ++j) {
      for(int k = 0; k <= pref[n][2]; ++k) {
        for(int x = 0; x < 3; ++x) f[i][j][k][x] = 1e9;
      }
    }
  }
  for(int i = 0; i < 3; ++i) f[0][0][0][i] = 0;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j <= min(pref[n][0], i); ++j) {
      for(int k = 0; k <= min(pref[n][1], i - j); ++k) {
        int l = i - j - k;
        if(l > pref[n][2]) continue;
        if(j < pref[n][0]) {
          long long cur = min(f[j][k][l][1], f[j][k][l][2]);
          cur += max(0, pref[pos[0][j]][1] - k) + max(0, pref[pos[0][j]][2] - l);
          
          f[j + 1][k][l][0] = min(f[j + 1][k][l][0], cur);
        }
        if(k < pref[n][1]) {
          long long cur = min(f[j][k][l][0], f[j][k][l][2]);
          cur += max(0, pref[pos[1][k]][0] - j) + max(0, pref[pos[1][k]][2] - l);
          
          f[j][k + 1][l][1] = min(f[j][k + 1][l][1], cur);
        }
        if(l < pref[n][2]) {
          long long cur = min(f[j][k][l][1], f[j][k][l][0]);
          cur += max(0, pref[pos[2][l]][1] - k) + max(0, pref[pos[2][l]][0] - j);
          
          f[j][k][l + 1][2] = min(f[j][k][l + 1][2], cur);
        }
      }
    }
  }
  
  long long res = 1e9;
  for(int i = 0; i < 3; ++i) {
    res = min(res, f[pref[n][0]][pref[n][1]][pref[n][2]][i]);
  }
  cout << (res == 1e9 ? -1 : res);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25