Submission #1197078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197078		aykhn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	153 ms	4500 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 4e2 + 5;

int dp[MXN][MXN][3];
int ndp[MXN][MXN][3];

void _()
{
  int n;
  cin >> n;
  int a[n + 1];
  vector<int> idx[3] = {{0}, {0}, {0}};
  vector<int> up[3][3];
  for (int i = 1; i <= n; i++)
  {
    char ch;
    cin >> ch;
    a[i] = (ch == 'R' ? 0 : ch == 'G' ? 1 : 2);
    idx[a[i]].push_back(i);
  }
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      for (int &k : idx[i])
      {
        up[i][j].push_back(upper_bound(idx[j].begin(), idx[j].end(), k) - idx[j].begin());
      }
    }
  }
  for (int i = 0; i < MXN; i++) for (int j = 0; j < MXN; j++) for (int l = 0; l < 3; l++) dp[i][j][l] = inf;
  if (idx[0].size() > 1) dp[1][0][0] = idx[0][1] - 1;
  if (idx[1].size() > 1) dp[0][1][1] = idx[1][1] - 1;
  if (idx[2].size() > 1) dp[0][0][2] = idx[2][1] - 1;
  for (int all = 1; all < n; all++)
  {
    for (int i = 0; i < MXN; i++) for (int j = 0; j < MXN; j++) for (int l = 0; l < 3; l++) ndp[i][j][l] = inf;
    for (int a = 0; a < idx[0].size(); a++)
    {
      for (int b = 0; b < idx[1].size(); b++)
      {
        int c = all - a - b;
        if (c >= idx[2].size()) continue;
        for (int l = 0; l < 3; l++)
        {
          if (l != 0 && a + 1 < idx[0].size())
          {
            int val = max(0, up[0][1][a + 1] - b - 1) + max(0, up[0][2][a + 1] - c - 1);
            ndp[a + 1][b][0] = min(ndp[a + 1][b][0], dp[a][b][l] + val);
          }
          if (l != 1 && b + 1 < idx[1].size())
          {
            int val = max(0, up[1][0][b + 1] - a - 1) + max(0, up[1][2][b + 1] - c - 1);
            ndp[a][b + 1][1] = min(ndp[a][b + 1][1], dp[a][b][l] + val);
          }
          if (l != 2 && c + 1 < idx[2].size())
          {
            int val = max(0, up[2][0][c + 1] - a - 1) + max(0, up[2][1][c + 1] - b - 1);
            ndp[a][b][2] = min(ndp[a][b][2], dp[a][b][l] + val);
          }
        }
      }
    }
    for (int i = 0; i < MXN; i++) for (int j = 0; j < MXN; j++) for (int l = 0; l < 3; l++) dp[i][j][l] = ndp[i][j][l];
  }
  int res = *min_element(dp[(int)idx[0].size() - 1][(int)idx[1].size() - 1], dp[(int)idx[0].size() - 1][(int)idx[1].size() - 1] + 3);
  cout << (res >= inf ? -1 : res) << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

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