Submission #927874

#	Time	Username	Problem	Language	Result	Execution time	Memory
927874		shart23	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	296 ms	780636 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

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

using namespace std;

const int MAXN = 405;
const int INF = 1e9;

int dp[MAXN][MAXN][MAXN][3];

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 0; i < MAXN; ++i) {
    for (int j = 0; j < MAXN; ++j) {
      for (int k = 0; k < MAXN; ++k) {
        for (int last = 0; last < 3; ++last) {
          dp[i][j][k][last] = INF;
        }
      }
    }
  }
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    a[i] = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
  }
  vector<vector<int>> pref(3, vector<int>(n + 1));
  array<vector<int>, 3> inds;
  for (int i = 0; i < n; ++i) {
    inds[a[i]].push_back(i);
    pref[a[i]][i + 1] = 1;
    pref[0][i + 1] += pref[0][i];
    pref[1][i + 1] += pref[1][i];
    pref[2][i + 1] += pref[2][i];
  }
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = 0;
  dp[0][0][0][2] = 0;
  for (int r = 0; r <= pref[0].back(); ++r) {
    for (int g = 0; g <= pref[1].back(); ++g) {
      for (int y = 0; y <= pref[2].back(); ++y) {
        for (int last = 0; last < 3; ++last) {
          if (last == 0 && r > 0) {
            int pos = inds[0][r - 1];
            dp[r][g][y][last] = min(dp[r][g][y][last], min(dp[r - 1][g][y][1], dp[r - 1][g][y][2]) + max(0, pref[1][pos] - g) + max(0, pref[2][pos] - y));
          }
          if (last == 1 && g > 0) {
            int pos = inds[1][g - 1];
            dp[r][g][y][last] = min(dp[r][g][y][last], min(dp[r][g - 1][y][0], dp[r][g - 1][y][2]) + max(0, pref[0][pos] - r) + max(0, pref[2][pos] - y));
          }
          if (last == 2 && y > 0) {
            int pos = inds[2][y - 1];
            dp[r][g][y][last] = min(dp[r][g][y][last], min(dp[r][g][y - 1][0], dp[r][g][y - 1][1]) + max(0, pref[0][pos] - r) + max(0, pref[1][pos] - g));
          }
        }
      }
    }
  }
  int r = pref[0].back();
  int g = pref[1].back();
  int y = pref[2].back();
  int ans = min(dp[r][g][y][0], min(dp[r][g][y][1], dp[r][g][y][2]));
  cout << (ans == INF ? -1 : ans) << '\n';
}

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