Submission #825468

#	Time	Username	Problem	Language	Result	Execution time	Memory
825468		taher	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	198 ms	207080 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "C:\GCC\debug.h"
#else
#define debug(...) void(42)
#endif

int Convert(char c) {
  if (c == 'R') {
    return 0;
  }
  if (c == 'G') {
    return 1;
  }
  return 2;
}

const int inf = 166789;
const int N = 402;

int dp[N][N][N][3];
int lb[N][3];
vector<int> at[3];

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

  int n;
  cin >> n;
  string s;
  cin >> s;

  vector<int> cnt(26);
  for (int i = 0; i < n; i++) {
    cnt[s[i] - 'A'] += 1;
  }
  vector<int> order(26);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return cnt[i] > cnt[j];
  });
  vector<char> trans(26);
  trans[order[0]] = 'Y';
  trans[order[1]] = 'G';
  trans[order[2]] = 'R';
  for (int i = 0; i < n; i++) {
    s[i] = trans[s[i] - 'A'];
  }

  for (int i = 0; i < n; i++) {
    at[Convert(s[i])].push_back(i);
  }

  lb[0][0] = lb[0][1] = lb[0][2] = 0;
  lb[0][Convert(s[0])] = 1;

  for (int i = 1; i < n; i++) {
    lb[i][0] = lb[i - 1][0];
    lb[i][1] = lb[i - 1][1];
    lb[i][2] = lb[i - 1][2];
    lb[i][Convert(s[i])] += 1;
  }


  auto Advance = [&](int loc, int type, int nR, int nG, int nY) {
    int bRs = max(0, nR - lb[loc][0]);
    int bGs = max(0, nG - lb[loc][1]);
    int bYs = max(0, nY - lb[loc][2]);
    if (type == 0) {
      return loc + max(0, bGs) + max(0, bYs);
    } else if (type == 1) {
      return loc + max(0, bRs) + max(0, bYs);
    }
    return loc + max(0, bRs) + max(0, bGs);
  };

  for (int i = 0; i <= (int) at[0].size(); i++) {
    for (int j = 0; j <= (int) at[1].size(); j++) {
      for (int p = 0; p <= 2; p++) {
        dp[n][i][j][p] = 0;
      }
    }
  }

  for (int i = n - 1; i >= 0; i--) {
    for (int nR = min((int) at[0].size(), i); nR >= 0; nR--) {
      for (int nG = min(i - nR, (int) at[1].size()); nG >= 0; nG--) {
        dp[i][nR][nG][0] = dp[i][nR][nG][1] = dp[i][nR][nG][2] = inf;

        auto Compute = [&](int previous_char) {
          int nY = i  - (nR + nG);
          int ans = inf;
          if (nR < (int) at[0].size() && previous_char != 0) {
            ans = min(ans, dp[i + 1][nR + 1][nG][0] + max(0, Advance(at[0][nR], 0, nR, nG, nY) - i));
          }
          if (nG < (int) at[1].size() && previous_char != 1) {
            ans = min(ans, dp[i + 1][nR][nG + 1][1] + max(0, Advance(at[1][nG], 1, nR, nG, nY) - i));
          }
          if (nY < (int) at[2].size() && previous_char != 2) {
            ans = min(ans, dp[i + 1][nR][nG][2] + max(0, Advance(at[2][nY], 2, nR, nG, nY) - i));
          }
          return ans;
        };


        if (i > 0) {
          for (int previous_char = 0; previous_char <= 2; previous_char++) {
            dp[i][nR][nG][previous_char] = min(dp[i][nR][nG][previous_char], Compute(previous_char));
          }
        } else {
          dp[i][nR][nG][0] = min(dp[i][nR][nG][0], Compute(-1));
        }
      }
    }
  }

  if (dp[0][0][0][0] == inf) {
    cout << -1 << '\n';
  } else {
    cout << dp[0][0][0][0] << '\n';
  }
  return 0;
}

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