Submission #1266244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266244		witek_cpp	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	128 ms	255388 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N; string S;
  if (!(cin >> N >> S)) return 0;

  vector<int> pos[3];
  auto id = [&](char c){ return c=='R'?0 : c=='G'?1 : 2; };
  for (int i=0;i<N;i++) pos[id(S[i])].push_back(i);

  int C[3] = { (int)pos[0].size(), (int)pos[1].size(), (int)pos[2].size() };
  // szybki filtr
  if (*max_element(C,C+3) > (N+1)/2) { cout << -1 << "\n"; return 0; }

  // prefLess[c][t][d]
  vector prefLess(3, vector(C[0]+C[1]+C[2]+1, array<int,3>{}));
  // zrobimy per kolor oddzielnie, bo t ma różny zakres
  vector<vector<array<int,3>>> pref(3);
  for (int c=0;c<3;c++){
    int T=C[c];
    pref[c].assign(T, {0,0,0});
    for (int t=0;t<T;t++){
      int p = pos[c][t];
      for (int d=0; d<3; d++) {
        // liczba d przed p:
        pref[c][t][d] = lower_bound(pos[d].begin(), pos[d].end(), p) - pos[d].begin();
      }
    }
  }

  // dp[r][g][m][last] -> kompresujemy last w 4, last=3 => NONE
  static int dp[401][401][401][4];
  for (int r=0;r<=C[0];r++)
    for (int g=0;g<=C[1];g++)
      for (int m=0;m<=N;m++)
        for (int l=0;l<4;l++)
          dp[r][g][m][l]=INF;
  dp[0][0][0][3]=0;

  auto getY = [&](int r,int g,int m){ return m - r - g; };

  for (int r=0; r<=C[0]; r++)
    for (int g=0; g<=C[1]; g++)
      for (int m=0; m<=N; m++){
        int y = getY(r,g,m);
        if (y<0 || y>C[2]) continue;
        for (int last=0; last<4; last++){
          int cur = dp[r][g][m][last];
          if (cur==INF) continue;
          int a[3] = {r,g,y};
          for (int c=0;c<3;c++){
            if (last==c) continue;
            if (a[c] >= C[c]) continue; // brak
            int t = a[c]; // 0-index na wektorach
            int add = 0;
            for (int d=0; d<3; d++) {
              int need = pref[c][t][d] - a[d];
              if (need>0) add += need;
            }
            int nr=r, ng=g, nm=m+1;
            if (c==0) nr++; else if (c==1) ng++;
            // y zwiększy się implikacyjnie przez m
            dp[nr][ng][nm][c] = min(dp[nr][ng][nm][c], cur + add);
          }
        }
      }

  int ans = INF;
  for (int last=0; last<3; last++)
    ans = min(ans, dp[C[0]][C[1]][N][last]);
  cout << (ans==INF ? -1 : ans) << "\n";
}

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