Submission #1097896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097896		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	76 ms	164948 KiB

joi2019_ho_t3

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
#include<bits/stdc++.h>
// #include "stress.cpp"
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
// #define endl "\n"
#define int ll
#define F first     
#define S second
#define db long double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
#define all(x) x.begin(),x.enad();
using namespace std;
const   ll inf = 1e18,MOD=1e9+7,N=400+10,MN=1e9+7,lim=100;
const db Pie=acos(-1);
int binpow(int a,int p);
int lcgayletiar(int a,int b);
//...and justice for all
int cnt[3];
int pr[3][N];
int in[N][3];
int dp[N][N][N][3];
const void solve(){
  int n;
  cin>>n;
  string c;
  cin>>c;
  for(int i=0;i<n;i++){
    if(i!=0){
      pr[0][i]=pr[0][i-1];
      pr[1][i]=pr[1][i-1];
      pr[2][i]=pr[2][i-1];
    }
    if(c[i]=='R'){
      
      pr[0][i]++;
      cnt[0]++;
      in[cnt[0]][0]=i;
    }
    if(c[i]=='G'){
      
      pr[1][i]++;
      cnt[1]++;
      in[cnt[1]][1]=i;
    }
    if(c[i]=='Y'){
      
      pr[2][i]++;
      cnt[2]++;
      in[cnt[2]][2]=i;
    }
  }
  for(int i=0;i<=cnt[0];i++){
    for(int j=0;j<=cnt[1];j++){
      for(int k=0;k<=cnt[2];k++){
        for(int l=0;l<3;l++){
          dp[i][j][k][l]=inf;
        }
      }
    }
  }
  dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
  for(int i=0;i<=cnt[0];i++){
    for(int j=0;j<=cnt[1];j++){
      for(int k=0;k<=cnt[2];k++){
        if(i){
          int cur=in[i][0]+1-(i+j+k);
          cur+=max(j-pr[1][in[i][0]],0ll);
          cur+=max(k-pr[2][in[i][0]],0ll);
          dp[i][j][k][0]=min({dp[i][j][k][0],dp[i-1][j][k][1]+cur,dp[i-1][j][k][2]+cur});
          // cout<<i<<" "<<j<<" "<<k<<" "<<cur<<" "<<pr[1][in[i][0]]<<endl;
        }
        if(j){
          int cur=in[j][1]+1-(i+j+k);
          cur+=max(i-pr[0][in[j][1]],0ll);
          cur+=max(k-pr[2][in[j][1]],0ll);
          dp[i][j][k][1]=min({dp[i][j][k][1],dp[i][j-1][k][0]+cur,dp[i][j-1][k][2]+cur});
        }
        if(k){
          int cur=in[k][2]+1-(i+j+k);
          cur+=max(i-pr[0][in[k][2]],0ll);
          cur+=max(j-pr[1][in[k][2]],0ll);
          dp[i][j][k][2]=min({dp[i][j][k][2],dp[i][j][k-1][0]+cur,dp[i][j][k-1][1]+cur});
        }
      }
      // cout<<endl;
    }
    // cout<<endl;
  }
  int ans=min({dp[cnt[0]][cnt[1]][cnt[2]][0],dp[cnt[0]][cnt[1]][cnt[2]][1],dp[cnt[0]][cnt[1]][cnt[2]][2]});
  if(ans==inf){
    cout<<-1<<endl;
  }
  else{
    cout<<ans<<endl;
  }
}
signed main() {
    srand(time(NULL));
    IOS;
    // freopen("sequence.in", "r", stdin);
    // freopen("sequence.out", "w", stdout);
    int pantyandstocking=1;
    // cin>>pantyandstocking;
    for(int i=1;i<=pantyandstocking;i++) { 
      // cout<<"Test "<<i<<": "<<endl;  
      solve(); 
      // cout<<endl;
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<"Time:"<<1000*((double)clock())/(double)  CLOCKS_PER_SEC<<"ms\n"; 
}
int lcgayletiar(int a,int b){return (a*b)/(int)__gcd(a,b);}
int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

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