Submission #825469

#	Time	Username	Problem	Language	Result	Execution time	Memory
825469		taher	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	474 ms	1017568 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 = 123456789;
const int N = 402;

int dp[N][N][N][4];
int lb[N][3];

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

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

  vector<vector<int>> at(3);
  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 index_of_char, int type, int nR, int nG, int nY) {
    if (type == 0) {
      int bigger_gs = nG - lb[index_of_char][1];
      int bigger_ys = nY - lb[index_of_char][2];
      return index_of_char + max(0, bigger_gs) + max(0, bigger_ys);
    } else if (type == 1) {
      int bigger_rs = nR - lb[index_of_char][0];
      int bigger_ys = nY - lb[index_of_char][2];
      return index_of_char + max(0, bigger_rs) + max(0, bigger_ys);
    } else {
      int bigger_rs = nR - lb[index_of_char][0];
      int bigger_gs = nG - lb[index_of_char][1];
      return index_of_char + max(0, bigger_rs) + max(0, bigger_gs);
    }
  };

  memset(dp, -1, sizeof(dp));

  function<int(int, int, int, int)> DP = [&](int i, int nR, int nG, int previous_char) {
    if (i == n) {
      return 0;
    }

    if (dp[i][nR][nG][previous_char] != -1) {
      return dp[i][nR][nG][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 dp[i][nR][nG][previous_char] = ans;
  };

  int res = DP(0, 0, 0, 3);
  if (res == inf) {
    cout << -1 << '\n';
  } else {
    cout << res << '\n';
  }
  return 0;
}

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