Submission #1039688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039688		Otalp	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	86 ms	164136 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

const int INF = 1e9 + 10;

int dp[401][401][401][3];
int a[401];
int cnt[401][3];
vector<int> q[3];

void solve(){
    int n;
    cin>>n;
    int cnt0 = 0, cnt1 = 0, cnt2 = 0;
    for(int i=1; i<=n; i++){
        char c;
        cin>>c;
        if(c == 'R') a[i] = 0, cnt0 ++;
        else if(c == 'G') a[i] = 1, cnt1 ++;
        else a[i] = 2, cnt2 ++;
    }
    for(int i=1; i<=n; i++){
        q[a[i]].pb(i);
        for(int d=0; d<3; d++){
            cnt[i][d] = cnt[i-1][d] + (a[i] == d);
        }
    }
    for(int i=0; i<=cnt0; i++){
        for(int j=0; j<=cnt1; j++){
            for(int k=0; k<=cnt2; k++){
                for(int d=0; d<=2; d++){
                    dp[i][j][k][d] = INF;
                }
            }
        }
    }
    for(int d=0; d<3; d++) dp[0][0][0][d] = 0;
    for(int i=0; i<n; i++){
        for(int x=0; x<=min(i, cnt0); x++){
            for(int y=0; y<=min(i-x, cnt1); y++){
                int z = i - x - y;
                if(z > cnt2) continue;
                if(x < cnt0)dp[x+1][y][z][0] = min(dp[x+1][y][z][0], min(dp[x][y][z][1], dp[x][y][z][2])+\
                                   max(0, cnt[q[0][x]][1] - y) + max(0, cnt[q[0][x]][2] - z));
                if(y < cnt1)dp[x][y+1][z][1] = min(dp[x][y+1][z][1], min(dp[x][y][z][0], dp[x][y][z][2])+\
                                   max(0, cnt[q[1][y]][0] - x) + max(0, cnt[q[1][y]][2] - z));
                if(z < cnt2)dp[x][y][z+1][2] = min(dp[x][y][z+1][2], min(dp[x][y][z][1], dp[x][y][z][0])+\
                                   max(0, cnt[q[2][z]][1] - y) + max(0, cnt[q[2][z]][0] - x));
            }
        }
    }
    int ans = INF;
    for(int i=0; i<3; i++){
        ans = min(ans, dp[cnt0][cnt1][cnt2][i]);
    }
    if(ans < INF) cout<<ans;
    else cout<<-1;



    

}

signed main(){
    solve();
}

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