Submission #1323334

#TimeUsernameProblemLanguageResultExecution timeMemory
1323334nambanana987Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
100 / 100
74 ms194328 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define f first
#define s second
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int N=405;
int n;
string s;
int cntR,cntG,cntY;
int pre[3][N]; //số phần tử X từ 1 ->i;
int id[3][N]; //vi tri cua phần tử x thứ i
int dp[3][N][N][N];
const int INF=INT_MAX-50;
void presolve(){
    for(int i=1;i<=n;++i){
        for(int j=0;j<3;++j) pre[j][i]+=pre[j][i-1];
        if(s[i]=='R'){
            ++cntR;
            ++pre[0][i];
            id[0][cntR]=i;
        }
        if(s[i]=='G'){
            ++cntG;
            ++pre[1][i];
            id[1][cntG]=i;
        }
        if(s[i]=='Y'){
            ++cntY;
            ++pre[2][i];
            id[2][cntY]=i;
        }

    }
    for (int c = 0; c < 3; ++c)
        for (int r = 0; r <= cntR; ++r)
            for (int g = 0; g <= cntG; ++g)
                for (int y = 0; y <= cntY; ++y)
                    dp[c][r][g][y] = INF;

    for (int c = 0; c < 3; ++c)
        dp[c][0][0][0] = 0;
}

void solve(){
    cin>>n>>s;
    s='%'+s;
    presolve();
    for(int i=0;i<=cntR;++i){
        for(int j=0;j<=cntG;++j){
            for(int k=0;k<=cntY;++k){
                for(int cur=0;cur<3;++cur){
                     if (dp[cur][i][j][k] == INF) continue;
                    for(int nx=0;nx<3;++nx){
                        if(cur==nx) continue;
                        if(i==cntR && nx==0)continue;
                        if(j==cntG && nx==1)continue;
                        if(k==cntY && nx==2)continue;
            
                        int nr=i,ng=j,ny=k;
                        int c=0;
                        if(nx==0){
                         
                            ++nr;
                            c+=max(0,ng-pre[1][id[0][nr]]);
                            c+=max(0,ny-pre[2][id[0][nr]]);
                        }
                        if(nx==1){

                            ++ng;
                            c+=max(0,nr-pre[0][id[1][ng]]);
                            c+=max(0,ny-pre[2][id[1][ng]]);
                        }
                        if(nx==2){
                      
                            ++ny;
                            c+=max(0,ng-pre[1][id[2][ny]]);
                            c+=max(0,nr-pre[0][id[2][ny]]);
                        }
                        dp[nx][nr][ng][ny]=min(dp[nx][nr][ng][ny],dp[cur][i][j][k]+c);
                    }
                }
                
            }
        }
    }
    int res = INF;
    for (int i = 0; i <= 2; ++i)
        res = min(res, dp[i][cntR][cntG][cntY]);
    cout << (res == INF ? -1 : res);
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...