Submission #1089011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089011		dpsaveslives	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	68 ms	230992 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
int dp[405][405][405][3];
int cnt[405][3],arr[405];
vector<int> inds[3];
const int INF = 1e9+9;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; cin >> N;
    string s; cin >> s; //R is 0, G is 1, Y is 2
    int cnt0 = 0, cnt1 = 0, cnt2 = 0;
    for(int i = 1;i<=N;++i){
        if(s[i-1] == 'R'){
            arr[i] = 0;
            ++cnt0;
        }
        else if(s[i-1] == 'G'){
            arr[i] = 1;
            ++cnt1;
        }
        else{
            arr[i] = 2;
            ++cnt2;
        }
    }
    for(int i = 0;i<=cnt0;++i){
        for(int j = 0;j<=cnt1;++j){
            for(int k = 0;k<=cnt2;++k){
                for(int l = 0;l<3;++l){
                    dp[i][j][k][l] = INF;
                }
            }
        }
    }
    for(int i = 0;i<3;++i) dp[0][0][0][i] = 0;
    for(int i = 1;i<=N;++i){
        inds[arr[i]].push_back(i);
        for(int j = 0;j<3;++j){
            cnt[i][j] = cnt[i-1][j]+(arr[i]==j);
        }
    }
    for(int i = 0;i<N;++i){
        for(int j = 0;j<=min(i,cnt0);++j){
            for(int k = 0;k<=min(i-j,cnt1);++k){
                int l = i-j-k;
                if(l > cnt2) continue;
                if(j < cnt0){
                    dp[j+1][k][l][0] = min(dp[j+1][k][l][0],min(dp[j][k][l][1],dp[j][k][l][2])+max(0,cnt[inds[0][j]][1]-k)+max(0,cnt[inds[0][j]][2]-l));
                }
                if(k < cnt1){
                    dp[j][k+1][l][1] = min(dp[j][k+1][l][1],min(dp[j][k][l][0],dp[j][k][l][2])+max(0,cnt[inds[1][k]][0]-j)+max(0,cnt[inds[1][k]][2]-l));
                }
                if(l < cnt2){
                    dp[j][k][l+1][2] = min(dp[j][k][l+1][2],min(dp[j][k][l][0],dp[j][k][l][1])+max(0,cnt[inds[2][l]][0]-j)+max(0,cnt[inds[2][l]][1]-k));
                }
            }
        }
    }
    int ans = INF;
    for(int i = 0;i<3;++i){
        ans = min(ans,dp[cnt0][cnt1][cnt2][i]);
    }
    if(ans != INF) cout << ans << "\n";
    else cout << -1 << "\n";
    return 0;
}

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