Submission #1180665

#TimeUsernameProblemLanguageResultExecution timeMemory
1180665user736482Growing Vegetable is Fun 3 (JOI19_ho_t3)C++20
60 / 100
1026 ms1114112 KiB
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,ans,bst,k,e,m,pier,h,w,u;
char ch;
ll dp[407][407][407][3];
vector<ll>v,pr[3];
ll gdzie[407][3];//gdzie ity jtego koloru

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    pr[0].pb(0);
    pr[1].pb(0);
    pr[2].pb(0);
    for(ll i=0;i<n;i++){
        cin>>ch;
        if(ch=='R')
            v.pb(0);
        else if(ch=='Y')
            v.pb(1);
        else
            v.pb(2);
        for(ll j =0;j<3;j++)pr[j].pb(pr[j].back());
        pr[v.back()].back()++;
        gdzie[pr[v.back()].back()][v.back()]=i+1;
    }//return 0;
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            for(ll k=0;k<3;k++){
                dp[i][j][0][k]=INFL;
                dp[i][0][j][k]=INFL;
                dp[0][i][j][k]=INFL;
            }
        }
    }//return 0;
    for(ll i=1;i<=n+1;i++){
        for(ll j=1;j<=n+1;j++){
            for(ll k=1;k<=n+1;k++){
                if(1==i && 1==j && 1==k){
                    continue;
                }
                for(ll l=0;l<3;l++){
                    dp[i][j][k][l]=INFL;
                    ll pom;
                    if(l==0)pom=i-1;
                    else if(l==1)pom=j-1;
                    else pom=k-1;
                    if(l!=0){
                        dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-(l==0)][j-(l==1)][k-(l==2)][0]+max(0LL,(ll)pr[1][gdzie[pom][l]]-j+1)+max(0LL,(ll)pr[2][gdzie[pom][l]]-k+1)+max(0LL,(ll)pr[0][gdzie[pom][l]]-i+1));
                    }
                    if(l!=1){
                        dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-(l==0)][j-(l==1)][k-(l==2)][1]+max(0LL,(ll)pr[1][gdzie[pom][l]]-j+1)+max(0LL,(ll)pr[2][gdzie[pom][l]]-k+1)+max(0LL,(ll)pr[0][gdzie[pom][l]]-i+1));
                    }
                    if(l!=2){
                        dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-(l==0)][j-(l==1)][k-(l==2)][2]+max(0LL,(ll)pr[1][gdzie[pom][l]]-j+1)+max(0LL,(ll)pr[2][gdzie[pom][l]]-k+1)+max(0LL,(ll)pr[0][gdzie[pom][l]]-i+1));
                    }
                    //cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<dp[i][j][k][l]<<"\n";
                }
            }
        }
    }
    pr[0].back()++;
    pr[1].back()++;
    pr[2].back()++;
    if(min(dp[pr[0].back()][pr[1].back()][pr[2].back()][0],min(dp[pr[0].back()][pr[1].back()][pr[2].back()][2],dp[pr[0].back()][pr[1].back()][pr[2].back()][1]))>1000000000)cout<<-1;
    else
    cout<<min(dp[pr[0].back()][pr[1].back()][pr[2].back()][0],min(dp[pr[0].back()][pr[1].back()][pr[2].back()][2],dp[pr[0].back()][pr[1].back()][pr[2].back()][1]));
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...