제출 #1197076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197076		aykhn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	397 ms	780440 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 4e2 + 5;

int dp[MXN][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 k = 0; k < MXN; k++) for (int l = 0; l < 3; l++) dp[i][j][k][l] = inf;
  if (idx[0].size() > 1) dp[1][0][0][0] = idx[0][1] - 1;
  if (idx[1].size() > 1) dp[0][1][0][1] = idx[1][1] - 1;
  if (idx[2].size() > 1) dp[0][0][1][2] = idx[2][1] - 1;
  for (int all = 1; all < n; all++)
  {
    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);
            dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], dp[a][b][c][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);
            dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], dp[a][b][c][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);
            dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], dp[a][b][c][l] + val);
          }
        }
      }
    }
  }
  int res = *min_element(dp[(int)idx[0].size() - 1][(int)idx[1].size() - 1][(int)idx[2].size() - 1], dp[(int)idx[0].size() - 1][(int)idx[1].size() - 1][(int)idx[2].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