Submission #788656

#	Time	Username	Problem	Language	Result	Execution time	Memory
788656		tvladm2009	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	51 ms	162952 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 4e2 + 7;
const int INF = (int) 1e9;
int n;
int a[N];
int cnt[3][N][3];
int dp[N][N][N][3];
string s;

int decode(char ch) {
  if (ch == 'R') {
    return 0;
  } else if (ch == 'G') {
    return 1;
  } else if (ch == 'Y') {
    return 2;
  }
  assert(0);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    a[i] = decode(s[i - 1]);    
  }
  int cnta = 0, cntb = 0, cntc = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0) {
      cnta++;
      cnt[0][cntc][1] = cntb;
      cnt[0][cntc][2] = cntc;
    } else if (a[i] == 1) {
      cntb++;
      cnt[1][cntb][0] = cnta;
      cnt[1][cntb][2] = cntc;
    } else {
      cntc++;
      cnt[2][cntc][0] = cnta;
      cnt[2][cntc][1] = cntb;
    }
  }
  for (int a = 0; a <= cnta; a++) {
    for (int b = 0; b <= cntb; b++) {
      for (int c = 0; c <= cntc; c++) {
        dp[a][b][c][0] = INF;
        dp[a][b][c][1] = INF;
        dp[a][b][c][2] = INF;
      }
    }
  }
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = 0;
  dp[0][0][0][2] = 0;
  for (int a = 0; a <= cnta; a++) {
    for (int b = 0; b <= cntb; b++) {
      for (int c = 0; c <= cntc; c++) {
        if (a < cnta) {
          dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], min(dp[a][b][c][1], dp[a][b][c][2]) + abs(b - cnt[0][a + 1][1]) + abs(c - cnt[0][a + 1][2]));
        }
        if (b < cntb) {
          dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], min(dp[a][b][c][0], dp[a][b][c][2]) + abs(a - cnt[1][b + 1][0]) + abs(c - cnt[1][b + 1][2]));
        }
        if (c < cntc) {
          dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], min(dp[a][b][c][0], dp[a][b][c][1]) + abs(a - cnt[2][c + 1][0]) + abs(b - cnt[2][c + 1][1]));
        }
      }
    }
  }
  int sol = INF;
  sol = min(sol, dp[cnta][cntb][cntc][0]);
  sol = min(sol, dp[cnta][cntb][cntc][1]);
  sol = min(sol, dp[cnta][cntb][cntc][2]);
  if (sol == INF) {
    cout << "-1\n";
    return 0;
  }
  cout << sol / 2;
  return 0;
}

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