Submission #1246108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246108		nasjes	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	135 ms	5732 KiB

joi2019_ho_t3

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e3+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m;
ll pos[5][dim];
ll a[dim];
ll pr[5][dim];
ll dp[5][450][450][3];
int main() {
    ll k, t, u0, v0;
    string s;
    cin>>n;
    cin>>s;
    ll cnt1=0;
    ll cnt2=0;
    ll cnt3=0;
    for(int i=1; i<=n; i++){
        if(s[i-1]=='R'){cnt1++;pos[1][cnt1]=i; a[i]=1;}
        else if(s[i-1]=='G'){cnt2++;pos[2][cnt2]=i; a[i]=2;}
        else {cnt3++; pos[3][cnt3]=i; a[i]=3;}
    }

    for(int last=1; last<=3; last++) {
        for (int r = 0; r <=cnt1; r++) {
            for (int j = 0; j <=  cnt2; j++) {
                dp[last][r][j][0]=inf;
                dp[last][r][j][1]=inf;
            }
        }
    }
    dp[1][0][0][0]=0;
    dp[2][0][0][0]=0;
    dp[3][0][0][0]=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=3; j++){
            pr[j][i]=pr[j][i-1];
        }
        pr[a[i]][i]++;
    }
    ll ans=inf;
    for(int i=0; i<=n; i++){
        for(int last=1; last<=3; last++) {
            for (int r = 0; r <= min<ll>(i, cnt1); r++) {
                for (int j = 0; j <= min<ll>(i-r, cnt2); j++) {
                    ll y = i- (r + j);
                    if(y<0)continue;
                    ll op1=inf, op2=inf, op3=inf;
                    if(r!=cnt1){
                        ll cur=pos[1][r+1];
                        ll tmp23=max<ll>(0, pr[2][cur]-j)+max<ll>(0, pr[3][cur]-y);
                        op1=tmp23;
                    }
                    if(j!=cnt2){
                        ll cur=pos[2][j+1];
                        ll tmp13=max<ll>(0, pr[1][cur]-r)+max<ll>(0, pr[3][cur]-y);
                        op2=tmp13;
                    }
                    if(y!=cnt3){
                        ll cur=pos[3][y+1];
                        ll tmp12=max<ll>(0, pr[1][cur]-r)+max<ll>(0, pr[2][cur]-j);
                        op3=tmp12;
                    }
                    if(last==1){
                        if(j!=cnt2)dp[2][r][j+1][1]=min(dp[last][r][j][0]+op2, dp[2][r][j+1][1]);
                        if(y!=cnt3)dp[3][r][j][1]=min(dp[last][r][j][0]+op3, dp[3][r][j][1]);

                    }
                    if(last==2){
                        if(r!=cnt1)dp[1][r+1][j][1]=min(dp[last][r][j][0]+op1, dp[1][r+1][j][1]);
                        if(y!=cnt2)dp[3][r][j][1]=min(dp[last][r][j][0]+op3, dp[3][r][j][1]);

                    }
                    if(last==3){

                        if(j!=cnt2)dp[2][r][j+1][1]=min(dp[last][r][j][0]+op2, dp[2][r][j+1][1]);
                        if(r!=cnt1)dp[1][r+1][j][1]=min(dp[last][r][j][0]+op1, dp[1][r+1][j][1]);

                    }
                   // cout<<last<<" "<<r<<" "<<j<<" "<<i-r-j<<endl;

                }

            }
        }
        for(int last=1; last<=3; last++) {
            for (int r = 0; r <= min<ll>(i+1, cnt1); r++) {
                for (int j = 0; j <= min<ll>(i+1 - r, cnt2); j++) {
                    ll y = i+1 - (r + j);
                    if(y<0)continue;
                 //   cout<<dp[last][r][j][1]<<" "<<last<<" -- "<<r<<" --  "<<j<<" -- "<<i+1-(r+j)<<endl;
                    dp[last][r][j][0]=dp[last][r][j][1];
                    if(i==n-1 && r==cnt1 && j==cnt2 && y==cnt3)ans=min(ans, dp[last][r][j][0]);
                    dp[last][r][j][1]=inf;
                }
            }
        }

    }
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;



    return 0;
}

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