제출 #953643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953643		Iliya_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	112 ms	104780 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;

const int N = 207, inf=1e9;
int A[N*2], dp[3][N][N][N],sum[3][N*2], te[3], po[3][N*2];


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;
               te[0]++; 
               po[0][te[0]]=i; 
          }
          else if(s[i]=='G'){
               A[i]=1;
               te[1]++; 
               po[1][te[1]]=i; 
          }
          else{
               A[i]=2; 
               te[2]++; 
               po[2][te[2]]=i; 
          }
     }
     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=0; i<3; i++){
          for(int j=1; j<=n; j++) sum[i][j]=sum[i][j-1]+(A[j]==i);
     }
     for(int id=0; id<3; id++) for(int a=0; a<N; a++) for(int b=0; b<N; b++) for(int c=0; c<N; c++) dp[id][a][b][c]=inf; 
     for(int i=0; i<3; i++) dp[i][0][0][0]=0; 
     for(int a=0; a<=te[0]; a++){
          for(int b=0; b<=te[1]; b++){
               for(int c=0; c<=te[2]; c++){
                    for(int now=0; now<3; now++){
                         for(int lst=0; lst<3; lst++){
                              if(lst==now||(a==te[0]&&now==0)||(b==te[1]&&now==1)||(c==te[2]&&now==2)) continue; 
                              int po0,po1,po2,fa,mn=dp[lst][a][b][c]; 
                              if(lst==0){
                                   po0=po[0][a]; 
                                   po1=(now==1?po[1][b+1]:po[2][c+1]); 
                                   po2=(now==1?po[2][c]:po[1][b]); 
                                   fa=(now==1?2:1);
                              }
                              else if(lst==1){
                                   po0=po[1][b]; 
                                   po1=(now==0?po[0][a+1]:po[2][c+1]); 
                                   po2=(now==0?po[2][c]:po[0][a]); 
                                   fa=(now==0?2:0); 
                              }
                              else{
                                   po0=po[2][c];  
                                   po1=(now==0?po[0][a+1]:po[1][b+1]);
                                   po2=(now==0?po[1][b]:po[0][a]); 
                                   fa=(now==0?1:0);
                              }
                              mn=mn+max(0,sum[lst][po1]-sum[lst][po0])+max(0,sum[fa][po1]-sum[fa][po2]); 
                              dp[now][a+(now==0)][b+(now==1)][c+(now==2)]=min(dp[now][a+(now==0)][b+(now==1)][c+(now==2)],mn);
                         }
                    }
               }
          }
     }
     int ans=inf; 
     for(int i=0; i<3; i++) ans=min(ans,dp[i][te[0]][te[1]][te[2]]); 
     cout<<(ans==inf?-1:ans)<<endl;

     return 0;
}

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