Submission #174408

#	Time	Username	Problem	Language	Result	Execution time	Memory
174408		AlexLuchianov	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	416 ms	238604 KiB

joi2019_ho_t3

#include <iostream>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 401;
int dp[1 + nmax][1 + nmax][1 + nmax][4];
int v[1 + nmax];
int lower[1 + nmax][4];
int pos[1 + nmax][4];

bool worth(int a, int b, int c){
  if(a + b + 1 < c)
    return 0;
  if(a + c + 1 < a)
    return 0;
  if(b + c + 1 < a)
    return 0;
  return 1;
}

int main()
{
  int n;
  cin >> n;
  for(int i = 1;i <= n; i++) {
    char ch;
    cin >> ch;
    if(ch == 'R')
      v[i] = 1;
    else if(ch == 'G')
      v[i] = 2;
    else if(ch == 'Y')
      v[i] = 3;
   lower[i][1] += lower[i - 1][1];
   lower[i][2] += lower[i - 1][2];
   lower[i][3] += lower[i - 1][3];
   lower[i][v[i]]++;
   pos[lower[i][v[i]]][v[i]] = i;
  }

  int red = lower[n][1], green = lower[n][2], yellow = lower[n][3];
  for(int i = 0; i <= red; i++)
    for(int j = 0; j <= green; j++)
      for(int h = 0; h <= yellow; h++)
        for(int last = 1; last <= 3; last++)
          dp[i][j][h][last] = nmax * nmax;
  dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][3] = 0;

  for(int total = 0; total < n; total++)
    for(int i = 0; i <= red; i++)
      for(int j = 0; j <= green; j++)
        if(i + j <= total){
          int h = total - i - j;
          if(worth(i, j, h) == 1){
            if(i < red){
              int pos2 = pos[i + 1][1];
              dp[i + 1][j][h][1] = MIN(dp[i + 1][j][h][1], MIN(dp[i][j][h][2], dp[i][j][h][3]) +
                                    MAX(0, lower[pos2][2] - j) +
                                    MAX(0, lower[pos2][3] - h)
                                    );
            }
            if(j < green){
              int pos2 = pos[j + 1][2];
              dp[i][j + 1][h][2] = MIN(dp[i][j + 1][h][2], MIN(dp[i][j][h][1], dp[i][j][h][3]) +
                                    MAX(0, lower[pos2][1] - i) +
                                    MAX(0, lower[pos2][3] - h)
                                    );
            }
            if(h < yellow){
              int pos2 = pos[h + 1][3];
              dp[i][j][h + 1][3] = MIN(dp[i][j][h + 1][3], MIN(dp[i][j][h][1], dp[i][j][h][2]) +
                                    MAX(0, lower[pos2][1] - i) +
                                    MAX(0, lower[pos2][2] - j)
                                    );
            }
          }
        }
  int result = MIN(dp[red][green][yellow][1], MIN(dp[red][green][yellow][2], dp[red][green][yellow][3]));
  if(result == nmax * nmax)
    cout << -1;
  else
    cout << result;
  return 0;
}

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