Submission #747823

#	Time	Username	Problem	Language	Result	Execution time	Memory
747823		tch1cherin	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	372 ms	134820 KiB

joi2019_ho_t3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> pos[3];
  for (int i = 0; i < n; i++) {
    if (s[i] == 'R') {
      pos[0].push_back(i);
    } else if (s[i] == 'G') {
      pos[1].push_back(i);
    } else {
      pos[2].push_back(i);
    }
  }
  int R = pos[0].size(), G = pos[1].size(), Y = pos[2].size();
  vector lb(3, vector<int>(n));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < n; j++) {
      lb[i][j] = lower_bound(pos[i].begin(), pos[i].end(), j) - pos[i].begin();
    }
  }
  vector dp(R + 1, vector(G + 1, vector(Y + 1, vector<int>(4, 1e9))));
  dp[0][0][0][3] = 0;
  for (int i = 0; i < n; i++) {
    for (int r = 0; r <= R && r <= i; r++) {
      for (int g = 0; g <= G && r + g <= i; g++) {
        int y = i - r - g;
        if (y > Y) {
          continue;
        }
        for (int l = 0; l < 4; l++) {
          if (l != 0 && r < R) {
            int a = lb[1][pos[0][r]], b = lb[2][pos[0][r]]; 
            dp[r + 1][g][y][0] = min(dp[r + 1][g][y][0], dp[r][g][y][l] + max(0, g - a) + max(0, y - b));
          }
          if (l != 1 && g < G) {
            int a = lb[0][pos[1][g]], b = lb[2][pos[1][g]]; 
            dp[r][g + 1][y][1] = min(dp[r][g + 1][y][1], dp[r][g][y][l] + max(0, r - a) + max(0, y - b));
          }
          if (l != 2 && y < Y) {
            int a = lb[0][pos[2][y]], b = lb[1][pos[2][y]]; 
            dp[r][g][y + 1][2] = min(dp[r][g][y + 1][2], dp[r][g][y][l] + max(0, r - a) + max(0, g - b));
          }
        } 
      }
    }
  }
  int ans = min({dp[R][G][Y][0], dp[R][G][Y][1], dp[R][G][Y][2]});
  cout << (ans == 1e9 ? -1 : ans) << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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