Submission #376301

#	Time	Username	Problem	Language	Result	Execution time	Memory
376301		Nima_Naderi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	458 ms	769132 KiB

joi2019_ho_t3

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

typedef long long ll;
const ll MXN = 400 + 3;
int n, cnt[3][MXN];
int dp[3][MXN][MXN][MXN];
vector<int> Pos[3];
string s;
inline void upd(int &x, int y){ if(x > y) x = y; }
inline int Calc(int ch, int a, int b, int c){
    int p = Pos[ch][(ch == 0 ? a : (ch == 1 ? b : c))];
    return max(0, cnt[0][p - 1] - a) + max(0, cnt[1][p - 1] - b) + max(0, cnt[2][p - 1] - c);;
}
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;
    if(cnt[0][n]) dp[0][1][0][0] = Calc(0, 0, 0, 0);
    if(cnt[1][n]) dp[1][0][1][0] = Calc(1, 0, 0, 0);
    if(cnt[2][n]) 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]){
                    ll ca = min(dp[1][a][b][c], dp[2][a][b][c]);
                    ca += Calc(0, a, b, c);
                    upd(dp[0][a + 1][b][c], ca);
                }
                if(b < cnt[1][n]){
                    ll ca = min(dp[0][a][b][c], dp[2][a][b][c]);
                    ca += Calc(1, a, b, c);
                    upd(dp[1][a][b + 1][c], ca);
                }
                if(c < cnt[2][n]){
                    ll ca = min(dp[0][a][b][c], dp[1][a][b][c]);
                    ca += Calc(2, a, b, c);
                    upd(dp[2][a][b][c + 1], ca);
                }
            }
        }
    }
    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: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25