Submission #938190

#	Time	Username	Problem	Language	Result	Execution time	Memory
938190		LittleOrange	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	541 ms	1048576 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT{
    ll n;
    vector<ll> a;
    BIT(ll N):n(N),a(N+1){}
    void add(ll i, ll x){
        for(;i<=n;i+=i&-i) a[i] += x;
    }
    ll get(ll i){
        ll x = 0;
        for(;i;i-=i&-i) x +=a[i];
        return x;
    }
};
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);
        }
    }
    vector<vector<vector<vector<ll>>>> dp(3,vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(n+5,vector<ll>(n+5,1e18))));
    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++){
                ll pos = i+j+k;
                if(i>0) dp[0][i][j][k] = min(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));
                if(j>0) dp[1][i][j][k] = min(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));
                if(k>0) dp[2][i][j][k] = min(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));
            }
        }
    }
    ll ans = 1e18;
    for(ll i = 0;i<3;i++) ans = min(ans,dp[i][cnt[0]][cnt[1]][cnt[2]]);
    cout << ans << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:47:20: warning: unused variable 'pos' [-Wunused-variable]
   47 |                 ll pos = i+j+k;
      |                    ^~~

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