제출 #1040967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1040967		khanhtb	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	57 ms	227664 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