Submission #1135531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135531		Hamed_Ghaffari	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	68 ms	31048 KiB

joi2019_ho_t3

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

using vi = vector<int>;
using vii = vector<vi>;
using viii = vector<vii>;

#define pb push_back
#define mins(a,b) (a = min(a,b))

const int MXN = 401;
const int INF = 1e9;

int n;
string s;
int ps[3][MXN];
viii dp[3];
vi pos[3];

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> s;
  pos[0].pb(-1); pos[1].pb(-1); pos[2].pb(-1);
  for(int i=0; i<n; i++) {
    if(i) for(int j : {0,1,2}) ps[j][i] = ps[j][i-1];
    ps[(s[i]=='R' ? 0 : (s[i]=='G' ? 1 : 2))][i]++;
    pos[(s[i]=='R' ? 0 : (s[i]=='G' ? 1 : 2))].pb(i);
  }
  for(int i : {0,1,2})
    dp[i] = viii(ps[0][n-1]+1, vii(ps[1][n-1]+1, vi(ps[2][n-1]+1, INF)));
  dp[0][0][0][0] = 0;
  int arr[3], arr2[3];
  for(arr[0]=0; arr[0]<=ps[0][n-1]; arr[0]++)
    for(arr[1]=0; arr[1]<=ps[1][n-1]; arr[1]++)
      for(arr[2]=0; arr[2]<=ps[2][n-1] && arr[0]+arr[1]+arr[2]<n; arr[2]++)
        for(int lst=0; lst<3; lst++)
          if(arr[0]+arr[1]+arr[2]==0 || arr[lst])
            for(int cur=0; cur<3; cur++)
              if((arr[0]+arr[1]+arr[2]==0 || lst!=cur) && arr[cur]<ps[cur][n-1]) {
                arr2[0] = arr[0];
                arr2[1] = arr[1];
                arr2[2] = arr[2];
                arr2[cur]++;
                mins(dp[cur][arr2[0]][arr2[1]][arr2[2]], 
                dp[lst][arr[0]][arr[1]][arr[2]]
                + max(0, arr2[0]-ps[0][pos[cur][arr2[cur]]])
                + max(0, arr2[1]-ps[1][pos[cur][arr2[cur]]])
                + max(0, arr2[2]-ps[2][pos[cur][arr2[cur]]]));
              }
  int res=INF;
  for(int lst=0; lst<3; lst++)
    mins(res, dp[lst][ps[0][n-1]][ps[1][n-1]][ps[2][n-1]]);
  cout << (res==INF ? -1 : res) << '\n';
  return 0;
}

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