Submission #542376

#	Time	Username	Problem	Language	Result	Execution time	Memory
542376		radal	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	300 ms	4300 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 4e2+20,mod = 1e9+7,inf = 1e9+10,maxm = (1 << 18)+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    }
    return z;
}
int dp[2][N][N][3];
int R[N],G[N],Y[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    rep(i,0,n){
        if (s[i] == 'R') R[i] = 1;
        if (s[i] == 'G') G[i] = 1;
        if (s[i] == 'Y') Y[i] = 1;
        if (i){
            R[i] += R[i-1];
            G[i] += G[i-1];
            Y[i] += Y[i-1];
        }
    }
    dp[0][0][0][2] = inf;
    dp[0][0][1][1] = inf;
    dp[0][1][0][0] = inf;
    rep(i,1,n){
        bool f = (i&1);
        rep(r,0,i+2){
            rep(g,0,i-r+2){
                rep(j,0,3) dp[f][r][g][j] = inf;
                if (R[n-1] < r || G[n-1] < g || Y[n-1] < i+1-r-g) continue;
                int lst[3] = {-1,-1,-1};
                lst[0] = lower_bound(R,R+n,r)-R;
                lst[1] = lower_bound(G,G+n,g)-G;
                lst[2] = lower_bound(Y,Y+n,i+1-r-g)-Y;
                if (r){
                    int count = max(0,g-G[lst[0]])+max(0,r-R[lst[0]])+max(0,i+1-r-g-Y[lst[0]]);
                    dp[f][r][g][1] = min(dp[f][r][g][1],count+dp[1-f][r-1][g][0]);
                    dp[f][r][g][2] = min(dp[f][r][g][2],count+dp[1-f][r-1][g][0]);
                }
                if (g){
                    int count = max(0,g-G[lst[1]])+max(0,r-R[lst[1]])+max(0,i+1-r-g-Y[lst[1]]);
                    dp[f][r][g][0] = min(dp[f][r][g][0],count+dp[1-f][r][g-1][1]);
                    dp[f][r][g][2] = min(dp[f][r][g][2],count+dp[1-f][r][g-1][1]);
                }
                if (i+1-g-r){
                    int count = max(0,g-G[lst[2]])+max(0,r-R[lst[2]])+max(0,i+1-r-g-Y[lst[2]]);
                    dp[f][r][g][1] = min(dp[f][r][g][1],count+dp[1-f][r][g][2]);
                    dp[f][r][g][0] = min(dp[f][r][g][0],count+dp[1-f][r][g][2]);
                }
            }
        }
    }
    bool f = (n-1)&1;
    int ans = inf;
    rep(j,0,3) ans = min(ans,dp[f][R[n-1]][G[n-1]][j]);
    if (ans == inf) cout << -1 << endl;
    else cout << ans;
}

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