제출 #1123427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1123427		irmuun	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	564 ms	757516 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);}

const int N=401,inf=1e9;

int dp[N][N][N][3];
int a[N],cnt[3];
int pos[3][N];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    cnt[0]=cnt[1]=cnt[2]=0;
    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;
        pos[a[i]][cnt[a[i]]]=i;
        cnt[a[i]]++;
    }
    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]=inf;
                }
            }
        }
    }
    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==inf){
        ans=-1;
    }
    cout<<ans;
}

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