Submission #1368327

#TimeUsernameProblemLanguageResultExecution timeMemory
1368327edoGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
32 ms2884 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

  int n;
  string s;
  cin >> n >> s;
  auto get_val = [&](char c) {
    if(c == 'R') return 0;
    else if(c == 'G') return 1;
    else return 2;
  };
  vector<int> pos[3];
  for(int i = 0; i < n; ++i) {
    pos[get_val(s[i])].emplace_back(i);
  }

  int cnt[3], mx = -1;
  for(int i = 0; i < 3; ++i) {
    cnt[i] = pos[i].size();
    mx = max(mx, cnt[i]);
  }

  if(2 * mx > n + 1) {
    cout << -1;
    return 0;
  }

  vector pref(3, vector<int>(n + 1, 0));
  for(int i = 0; i < n; ++i) {
    for(int c = 0; c < 3; ++c) {
      pref[c][i + 1] = pref[c][i];
    }
    pref[get_val(s[i])][i + 1]++;
  }


  const ll inf = (1ll << 60);
  vector dp(cnt[0] + 1, vector(cnt[1] + 1, array<ll, 4>{})), ndp(dp);

  auto set_val = [&](auto& a) {
    for(int i = 0; i <= cnt[0]; ++i) {
      for(int j = 0; j <= cnt[1]; ++j) {
        for(int z = 0; z < 4; ++z) {
          a[i][j][z] = inf;
        }
      }
    }
  };

  auto umin = [&](ll& a, ll b) {
    if(a > b) a = b;
  };

  auto get_cost = [&](int col, int id, int r, int g, int y) {
    int p = pos[col][id];
    int used[3] = {r, g, y};
    ll C = 0;
    for(int i = 0; i < 3; ++i) {
      C += max(0, pref[i][p] - used[i]);
    }
    return C;
  };

  set_val(dp);
  dp[0][0][3] = 0;
  for(int used = 0; used < n; ++used) {
    set_val(ndp);
    for(int r = 0; r <= cnt[0]; ++r) {
      for(int g = 0; g <= cnt[1]; ++g) {
        int y = used - r - g;
        if(y < 0 || y > cnt[2]) continue;
        for(int z = 0; z < 4; ++z) {
          ll cur = dp[r][g][z];
          if(cur == inf) continue;
          if(r < cnt[0] && z != 0) 
            umin(ndp[r + 1][g][0], cur + get_cost(0, r, r, g, y));
          if(g < cnt[1] && z != 1) 
            umin(ndp[r][g + 1][1], cur + get_cost(1, g, r, g, y));
          if(y < cnt[2] && z != 2) 
            umin(ndp[r][g][2], cur + get_cost(2, y, r, g, y));
        }
      }
    }
    dp.swap(ndp);
  }

  ll ans = inf;
  for(int i = 0; i < 3; ++i) 
    umin(ans, dp[cnt[0]][cnt[1]][i]);
  cout << ans;

  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...