Submission #938193

#	Time	Username	Problem	Language	Result	Execution time	Memory
938193		LittleOrange	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	162 ms	475248 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[3][405][405][405];
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    string s;
    cin >> n >> s;
    vector<ll> cnt(3,0);
    vector<ll> a(n);
    vector<vector<ll>> ps(3);
    for(ll i = 0;i<n;i++) {
        a[i] = s[i]=='R'?0:s[i]=='G'?1:2;
        cnt[a[i]]++;
        ps[a[i]].push_back(i+1);
    }
    for(ll i : cnt){
        if (i>(n+1)/2){
            cout << "-1\n";
            return 0;
        }
    }
    vector<vector<ll>> c(3,vector<ll>(n+1,0));
    for(ll i = 0;i<n;i++){
        for(ll j = 0;j<3;j++){
            c[j][i+1] = c[j][i] + (a[i]==j);
        }
    }
    dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
    for(ll i = 0;i<=cnt[0];i++){
        for(ll j = 0;j<=cnt[1];j++){
            for(ll k = 0;k<=cnt[2];k++){
                if (!(i|j|k)) continue;
                if(i>0) dp[0][i][j][k] = min(dp[1][i-1][j][k],dp[2][i-1][j][k])+max(c[0][ps[0][i-1]]-i,0ll)+max(c[1][ps[0][i-1]]-j,0ll)+max(c[2][ps[0][i-1]]-k,0ll);
                else dp[0][i][j][k] = big;
                if(j>0) dp[1][i][j][k] = min(dp[0][i][j-1][k],dp[2][i][j-1][k])+max(c[0][ps[1][j-1]]-i,0ll)+max(c[1][ps[1][j-1]]-j,0ll)+max(c[2][ps[1][j-1]]-k,0ll);
                else dp[1][i][j][k] = big;
                if(k>0) dp[2][i][j][k] = min(dp[0][i][j][k-1],dp[1][i][j][k-1])+max(c[0][ps[2][k-1]]-i,0ll)+max(c[1][ps[2][k-1]]-j,0ll)+max(c[2][ps[2][k-1]]-k,0ll);
                else dp[2][i][j][k] = big;
            }
        }
    }
    ll ans = big;
    for(ll i = 0;i<3;i++) ans = min(ans,dp[i][cnt[0]][cnt[1]][cnt[2]]);
    cout << ans << "\n";
}

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