Submission #541435

#	Time	Username	Problem	Language	Result	Execution time	Memory
541435		browntoad	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	83 ms	164960 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
 
const ll inf = (1ll<<60);
const int iinf=2147483647;
const ll mod = 998244353;
const ll maxn=405;
const double PI=acos(-1);
 
ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}
 
ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}
int dp[maxn][maxn][maxn][3];
int pos[3][maxn];
int cnt[3][maxn];
signed main(){
    IOS();
    int n; cin>>n;
    string str; cin>>str;
    str='$'+str;
    int tota=0, totb=0, totc=0;
    REP1(i,n){
        if (str[i]=='R') tota++;
        else if (str[i]=='G') totb++;
        else totc++;
    }
    REP(i,tota+1){
        REP(j,totb+1){
            REP(k,totc+1){
                REP(l, 3){
                    dp[i][j][k][l]=inf;
                }
                
            }
        }
    }
    REP1(i,n){
        REP(l, 3) cnt[l][i]=cnt[l][i-1];
        if (str[i]=='R') {
            cnt[0][i]++;
            pos[0][cnt[0][i]]=i;
        }
        else if (str[i]=='G') {
            cnt[1][i]++;
            pos[1][cnt[1][i]]=i;
        }
        else {
            cnt[2][i]++;
            pos[2][cnt[2][i]]=i;
        }
    }
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    // 0 is R, 1 is G, 2 is Y
    REP(i, tota+1){
        REP(j, totb+1){
            REP(k, totc+1){
                if (i+j+k==0) continue;
                if (i>0){
                    int p=pos[0][i]-1;
                    dp[i][j][k][0]=min(dp[i-1][j][k][1], dp[i-1][j][k][2]);
                    dp[i][j][k][0]+=p-min(i-1, cnt[0][p])-min(j, cnt[1][p])-min(k, cnt[2][p]);
                    dp[i][j][k][0]=min(dp[i][j][k][0], inf);
                }
                if (j>0){
                    int p=pos[1][j]-1;
                    dp[i][j][k][1]=min(dp[i][j-1][k][0], dp[i][j-1][k][2]);
                    dp[i][j][k][1]+=p-min(i, cnt[0][p])-min(j-1, cnt[1][p])-min(k, cnt[2][p]);
                    dp[i][j][k][1]=min(dp[i][j][k][1], inf);
                }
                if (k>0){
                    int p=pos[2][k]-1;
                    dp[i][j][k][2]=min(dp[i][j][k-1][0], dp[i][j][k-1][1]);
                    dp[i][j][k][2]+=p-min(i, cnt[0][p])-min(j, cnt[1][p])-min(k-1, cnt[2][p]);
                    dp[i][j][k][2]=min(dp[i][j][k][2], inf);
                }
            }
        }
    }
    int k=min({dp[tota][totb][totc][0], dp[tota][totb][totc][1], dp[tota][totb][totc][2]});
    if (k==inf) k=-1;
    cout<<k<<endl;
}
/*

3
YYG

*/

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