Submission #924080

#	Time	Username	Problem	Language	Result	Execution time	Memory
924080		MercubytheFirst	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	456 ms	757844 KiB

joi2019_ho_t3

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ll N = 105;
const ll inf = 1e9 + 37;
#define endl '\n'

/*
- have fun!
- monovariants?
- invariants?
- bs on ans?
- phrase it differently?
- quirky constraints? 
- dp? 
- greedy? 
- find slow solution and try to optimize?
*/

void solve(void){
  int n;
  string s;
  cin >> n >> s;
  s = "0" + s;
  for(int i = 1; i <= n; ++i){
    if(s[i] == 'R') s[i] = 0;
    else if(s[i] == 'G') s[i] = 1;
    else if(s[i] == 'Y') s[i] = 2;
  }
  vector<int> k[3];
  k[0].pb(0);
  k[1].pb(0);
  k[2].pb(0);
  for(int i = 1; i <= n; ++i)
    k[(int)s[i]].push_back(i);
  vector<array<int, 3> > pre(n + 1, array<int, 3>{0, 0, 0});
  for(int i = 1; i <= n; ++i){
    pre[i] = pre[i - 1];
    pre[i][s[i]]++;
  }
  int dp[n + 1][n + 1][n + 1][3];
  for(int r = 0; r <= n; ++r)
    for(int g = 0; g <= n; ++g)
      for(int y = 0; y <= n; ++y)
        for(int c = 0; c <3; ++c)
          dp[r][g][y][c] = inf;
  dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
  int c[3] = {0};
  // cout << pre[n][0] << ' ' << pre[n][1] << ' ' << pre[n][2] << endl;
  for(c[0] = 0; c[0] <= pre[n][0]; ++c[0]){
    for(c[1] = 0; c[1] <= pre[n][1]; ++c[1]){
      for(c[2] = 0; c[2] <= pre[n][2]; ++c[2]){
        for(int col = 0; col <3; ++col){
          if(!c[0] and !c[1] and !c[2])
            continue;
          int& ans = dp[c[0]][c[1]][c[2]][col];
          if(c[col] <= 0){
            // cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << col << endl;
            continue;
          }
          // cout << c[0] << ' ' << c[1] << ' ' << c[2] << ' ' << col << endl;
          int i = c[0] + c[1] + c[2];
          int ni = k[col][c[col]], d = 0;
          for(int j = 0; j <3 ; ++j){
            if(j == col)
              continue;
            d += (pre[ni][j] >= c[j] ? 0 : c[j] - pre[ni][j]);
          }
          ni += d;
          for(int j = 0; j <3; ++j){
            if(j == col)
              continue;
            ans = min(ans, dp[c[0] - (col == 0)][c[1] - (col == 1)][c[2] - (col == 2)][j] + ni - i);
          }
        }
      }
    }
  }
  int ans = inf;
  for(int i = 0; i < 3; ++i){
    ans = min(ans, dp[pre[n][0]][pre[n][1]][pre[n][2]][i]);
    // cout << dp[pre[n][0]][pre[n][1]][pre[n][2]][i] << ' ';
  }
  if(ans == inf)
    ans = -1;
  cout << ans << endl;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // signed t; cin >> t; while(t--)
    solve();
}

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