Submission #1135647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135647		Malek1387	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	354 ms	766780 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
void chmin(int& x,int y){x=min(x,y);}
const int maxn = 400;
int pre[maxn][3];
int dp[maxn+5][maxn+5][maxn+5][3];
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 if (s[i] == 'Y'){
            a[i]=2;
        }
        pos[a[i]].pb(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]=1e9;
                }
            }
        }
    }
    pre[0][0]=pre[0][1]=pre[0][2]=0;
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][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];
            if (a[i] == c){
                pre[i][c] += 1;
            }
        }
    }
    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(i<cnt[0] and c!=0){
                        int p=pos[0][i];
                        dp[i+1][j][k][0] = min(dp[i+1][j][k][0],dp[i][j][k][c]+max(pre[p][1]-j,0)+max(pre[p][2]-k,0));
                    }
                    if(k<cnt[2] and c!=2){
                        int p=pos[2][k];
                        dp[i][j][k+1][2] = min(dp[i][j][k+1][2],dp[i][j][k][c]+max(pre[p][0]-i,0)+max(pre[p][1]-j,0));
                    }
                    if(j<cnt[1] and c!=1){
                        int p=pos[1][j];
                        dp[i][j+1][k][1] = min(dp[i][j+1][k][1],dp[i][j][k][c]+max(pre[p][2]-k,0)+max(pre[p][0]-i,0));
                    }
                }
            }
        }
    }
    long long ans = 1e9;
    for (int i = 0 ; i < 3 ; i ++){
        ans = min (ans , dp[cnt[0]][cnt[1]][cnt[2]][i]*1ll);
    }
    if(ans == 1e9){
        ans=-1;
    }
    cout<<ans;
}

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