제출 #376289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376289		Nima_Naderi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	440 ms	809736 KiB

joi2019_ho_t3

///In the name of GOD
//#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 400 + 10;
int n, cnt[3][MXN];
int dp[3][MXN][MXN][MXN];
vector<int> Pos[3];
string s;
int Calc(int ch, int a, int b, int c){
    int now = 0, p = Pos[ch][(ch == 0 ? a : (ch == 1 ? b : c))];
    int ta = cnt[0][p - 1], tb = cnt[1][p - 1], tc = cnt[2][p - 1];
    now += max(0, ta - a);
    now += max(0, tb - b);
    now += max(0, tc - c);
    return now;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = "$" + s;
    memset(dp, 31, sizeof dp);
    for(int i = 1; i <= n; i ++){
        switch(s[i]){
            case 'R' : s[i] = 'A'; break;
            case 'G' : s[i] = 'B'; break;
            case 'Y' : s[i] = 'C'; break;
        }
        cnt[0][i] = cnt[0][i - 1];
        cnt[1][i] = cnt[1][i - 1];
        cnt[2][i] = cnt[2][i - 1];
        cnt[s[i] - 'A'][i] ++;
        Pos[s[i] - 'A'].push_back(i);
    }
    if(max({cnt[0][n], cnt[1][n], cnt[2][n]}) >= (n + 1) / 2)
        return cout << -1, 0;
    dp[0][1][0][0] = Calc(0, 0, 0, 0);
    dp[1][0][1][0] = Calc(1, 0, 0, 0);
    dp[2][0][0][1] = Calc(2, 0, 0, 0);
    for(int a = 0; a <= cnt[0][n]; a ++){
        for(int b = 0; b <= cnt[1][n]; b ++){
            for(int c = 0; c <= cnt[2][n]; c ++){
                if(a + b + c == 0) continue;
                if(a < cnt[0][n]){
                    int* DP = &dp[0][a + 1][b][c];
                    (*DP) = min((*DP), dp[1][a][b][c] + Calc(0, a, b, c));
                    (*DP) = min((*DP), dp[2][a][b][c] + Calc(0, a, b, c));
                }
                if(b < cnt[1][n]){
                    int* DP = &dp[1][a][b + 1][c];
                    (*DP) = min((*DP), dp[0][a][b][c] + Calc(1, a, b, c));
                    (*DP) = min((*DP), dp[2][a][b][c] + Calc(1, a, b, c));
                }
                if(c < cnt[2][n]){
                    int* DP = &dp[2][a][b][c + 1];
                    (*DP) = min((*DP), dp[0][a][b][c] + Calc(2, a, b, c));
                    (*DP) = min((*DP), dp[1][a][b][c] + Calc(2, a, b, c));
                }
            }
        }
    }
    int ans = dp[0][cnt[0][n]][cnt[1][n]][cnt[2][n]];
    ans = min(ans, dp[1][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
    ans = min(ans, dp[2][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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