Submission #1221479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221479		brover29	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	274 ms	689608 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
#define f first
#define s second
const ll N=3e5+29;
ll cnt[3],n,ans=1e18,pref[3][N],dp[405][405][405][3];
vector<ll>pos[3];
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>s;
    ll x=0;
    s=' '+s;
    for(char i:s){
        if(i==' ')continue;
        x++;
        for(ll i=0;i<3;i++){
            pref[i][x]+=pref[i][x-1];
        }
        if(i=='R'){
            cnt[0]++;
            pos[0].push_back(x);
            pref[0][x]++;
        }
        if(i=='Y'){
            cnt[1]++;
            pos[1].push_back(x);
            pref[1][x]++;

        }
        if(i=='G'){
            cnt[2]++;
            pos[2].push_back(x);
            pref[2][x]++;
        }
    }
    for(ll i=0;i<=n;i++){
        for(ll a=0;a<=cnt[0];a++){
            for(ll b=0;b<=cnt[1];b++){
                for(ll cur=0;cur<3;cur++)dp[i][a][b][cur]=1e18;
            }
        }
    }
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    for(ll i=1;i<=n;i++){
        for(ll a=0;a<=cnt[0];a++){
            for(ll b=0;b<=cnt[1];b++){
                if(a+b>i)continue;
                ll c=i-(a+b);
                if(c>cnt[2])continue;
                for(ll last=0;last<3;last++){
                    if(last!=0&&a){
                        ll j=pos[0][a-1];
                        ll cnt=max(0ll,b-pref[1][j])+max(0ll,c-pref[2][j]);
                        ll val = max(0ll, j + cnt - i);
                        dp[i][a][b][0]=min(dp[i][a][b][0],dp[i-1][a-1][b][last]+val);
                    }
                    if(last!=1&&b){
                        ll j=pos[1][b-1];
                        ll cnt=max(0ll,a-pref[0][j])+max(0ll,c-pref[2][j]);
                        ll val = max(0ll, j + cnt - i);
                        dp[i][a][b][1]=min(dp[i][a][b][1],dp[i-1][a][b-1][last]+val);
                    }
                    if(last!=2&&c){
                        ll j=pos[2][c-1];
                        ll cnt=max(0ll,b-pref[1][j])+max(0ll,a-pref[0][j]);
                        ll val = max(0ll, j + cnt - i);
                        dp[i][a][b][2]=min(dp[i][a][b][2],dp[i-1][a][b][last]+val);
                    }

                }
//                for (int last = 0; last < 3; ++ last) {
//                    cout << dp[i][a][b][last] << " ";
//                }
//                cout << "\n";
                if(i==n){
                    ans=min({ans,dp[i][a][b][0],dp[i][a][b][1],dp[i][a][b][2]});
                }
            }
        }
    }
    cout<<(ans==1e18 ? -1 : ans);
}

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