Submission #1180671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180671		user736482	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	282 ms	713668 KiB

joi2019_ho_t3

#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 1000000000000000099

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<=pr[0].back()+1;i++){
        for(ll j=1;j<=pr[1].back()+1;j++){
            for(ll k=1;k<=pr[2].back()+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]));
}

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