Submission #1123388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123388		irmuun	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	655 ms	780428 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

void chmin(int& x,int y){x=min(x,y);}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int>a(n),cnt(3,0);
    vector<int>pos[3];
    for(int i=0;i<n;i++){
        if(s[i]=='R') a[i]=0;
        else if(s[i]=='G') a[i]=1;
        else a[i]=2;
        cnt[a[i]]++;
        pos[a[i]].pb(i);
    }
    int dp[n+5][n+5][n+5][3];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                for(int c=0;c<3;c++){
                    dp[i][j][k][c]=1e9;
                }
            }
        }
    }
    int pre[n][3];
    pre[0][0]=pre[0][1]=pre[0][2]=0;
    pre[0][a[0]]++;
    for(int i=1;i<n;i++){
        for(int c=0;c<3;c++){
            pre[i][c]=pre[i-1][c]+(a[i]==c?1:0);
        }
    }
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    for(int i=0;i<=cnt[0];i++){
        for(int j=0;j<=cnt[1];j++){
            for(int k=0;k<=cnt[2];k++){
                for(int c=0;c<3;c++){
                    if(c!=0&&i<cnt[0]){
                        int p=pos[0][i];
                        chmin(dp[i+1][j][k][0],dp[i][j][k][c]+max(pre[p][1]-j,0)+max(pre[p][2]-k,0));
                    }
                    if(c!=1&&j<cnt[1]){
                        int p=pos[1][j];
                        chmin(dp[i][j+1][k][1],dp[i][j][k][c]+max(pre[p][2]-k,0)+max(pre[p][0]-i,0));
                    }
                    if(c!=2&&k<cnt[2]){
                        int p=pos[2][k];
                        chmin(dp[i][j][k+1][2],dp[i][j][k][c]+max(pre[p][0]-i,0)+max(pre[p][1]-j,0));
                    }
                }
            }
        }
    }
    int ans=min({dp[cnt[0]][cnt[1]][cnt[2]][0],dp[cnt[0]][cnt[1]][cnt[2]][1],dp[cnt[0]][cnt[1]][cnt[2]][2]});
    if(ans==1e9){
        ans=-1;
    }
    cout<<ans;
}

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