Submission #953593

#	Time	Username	Problem	Language	Result	Execution time	Memory
953593		Iliya_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	50 ms	29168 KiB

joi2019_ho_t3

//IN THE NAME OF GOD
#include<bits/stdc++.h>
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("sse4")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define mp          make_pair
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double dll;

#define int long long 
const int N = 67, inf=1e18;
int a[N], dp[2][N][N][N][3], te[3]; 
vector<int> po[3];


int32_t main(){
     fast_io;

     int n; cin>>n;
     string s; cin >> s; s='#'+s; 
     for(int i=1; i<=n; i++){
          if(s[i]=='R')a[i]=0; 
          else if(s[i]=='G')a[i]=1; 
          else a[i]=2; 
          po[a[i]].pb(i); 
     }
     for(int i=0; i<2; i++) for(int j=0; j<N; j++) for(int k=0; j<N; j++) for(int x=0; x<N; x++) for(int y=0; y<3; y++) dp[i][j][k][x][y]=inf; 
     dp[0][0][0][0][0]=dp[0][0][0][0][1]=dp[0][0][0][0][2]=0;
     for(int i=0; i<3; i++) te[i]=ll(po[i].size()); 
     if(te[0]>(te[1]+te[2]+1)||te[1]>(te[0]+te[2]+1)||te[2]>(te[0]+te[1]+1)) return cout<<-1<<endl,0;
     for(int i=1; i<=n; i++){
          int id=(i&1);
          for(int cnt0=0; cnt0<N; cnt0++) for(int cnt1=0; cnt1<N; cnt1++) for(int cnt2=0; cnt2<N; cnt2++) for(int j=0; j<3; j++) dp[id][cnt0][cnt1][cnt2][j]=inf;
          for(int cnt0=0; cnt0<=i; cnt0++){
               if(cnt0>te[0])continue;
               for(int cnt1=0; cnt0+cnt1<=i; cnt1++){
                    if(cnt1>te[1]) continue; 
                    int cnt2=i-cnt0-cnt1;
                    if(cnt2>te[2]) continue; 
                    for(int last=0; last<3; last++){
                         for(int now=0; now<3; now++){
                              if(last==now||(now==0&&cnt0==0)||(now==1&&cnt1==0)||(now==2&&cnt2==0)) continue; 
                              int hav=(now==0?cnt0:(now==1?cnt1:cnt2)); 
                              dp[id][cnt0][cnt1][cnt2][now]=min(dp[id][cnt0][cnt1][cnt2][now],dp[1-id][cnt0-(now==0)][cnt1-(now==1)][cnt2-(now==2)][last]+abs(i-po[now][hav-1]));
                         }
                    }
               }
          }
     }
     int ans=inf; 
     for(int i=0; i<3; i++) ans=min(ans,dp[(n&1)][te[0]][te[1]][te[2]][i]); 
     if(ans>=inf) return cout<<-1<<endl,0; 
     cout<<(ans/2)<<endl;

     return 0;
}

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