Submission #868840

#	Time	Username	Problem	Language	Result	Execution time	Memory
868840		Darren0724	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	309 ms	780644 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false);cin.tie(0);
#define all(x) x.begin(),x.end()
const int INF=1e9;
const int mod=998244353;
const int N=405;
int dp[3][405][405][405]{};
int32_t main(){
    LCBorz;
    int n;cin>>n;
    string s;cin>>s;
    int r=0,g=0,y=0;
    vector<pair<int,int>> r1,g1,y1;
    for(int i=0;i<n;i++){
        if(s[i]=='R'){
            r1.push_back({g,y});
            r++;
        }
        if(s[i]=='G'){
            g1.push_back({y,r});
            g++;
        }
        if(s[i]=='Y'){
            y1.push_back({r,g});
            y++;
        }
    }
    r1.push_back({0,0});
    g1.push_back({0,0});
    y1.push_back({0,0});
    for(int i=0;i<3;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                for(int p=0;p<N;p++){
                    dp[i][j][k][p]=INF;
                }
            }
        }
    }
    dp[0][0][0][0]=0;
    dp[1][0][0][0]=0;
    dp[2][0][0][0]=0;
    
    for(int i=0;i<=r;i++){
        for(int j=0;j<=g;j++){
            for(int k=0;k<=y;k++){
                //cout<<i<<' '<<j<<' '<<k<<' '<<endl;
                int r2=max((int)0,r1[i].first-j)+max((int)0,r1[i].second-k);
                int g2=max((int)0,g1[j].first-k)+max((int)0,g1[j].second-i);
                int y2=max((int)0,y1[k].first-i)+max((int)0,y1[k].second-j);
                dp[0][i+1][j][k]=min(dp[0][i+1][j][k],min(dp[1][i][j][k],dp[2][i][j][k])+r2);
                dp[1][i][j+1][k]=min(dp[1][i][j+1][k],min(dp[2][i][j][k],dp[0][i][j][k])+g2);
                dp[2][i][j][k+1]=min(dp[2][i][j][k+1],min(dp[0][i][j][k],dp[1][i][j][k])+y2);
            }
        }
    }
    int ans=min({dp[0][r][g][y],dp[1][r][g][y],dp[2][r][g][y]});
    cout<<(ans==INF?-1:ans)<<endl;


    return 0;
}

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