Submission #1160019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160019		fatman87878	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	44 ms	2116 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define all(x) (x).begin(),(x).end()
#define lb(x) ((x)&-(x))
#define IOS cin.tie(nullptr)->sync_with_stdio(0);

constexpr int maxN = 4e2+5;

int n,dp[2][maxN][maxN][3],others[3][maxN],pos[3][maxN],cnt[3];

string s;

inline int cal(int v1,int v2,int v3,int nxt){
    //cout<<v1<<' '<<v2<<' '<<v3<<' '<<nxt<<'\n';
    int ret = 0,p = 0;
    if(nxt==0)p = pos[0][v1+1];
    else if(nxt==1)p = pos[1][v2+1];
    else if(nxt==2)p = pos[2][v3+1];
    ret += max(0,others[0][p]-v1-(nxt==0));
    ret += max(0,others[1][p]-v2-(nxt==1));
    ret += max(0,others[2][p]-v3-(nxt==2));
    return ret;
}

inline void chmin(int& a,int b){
    a=min(a,b);
}

int main(){
    IOS
    cin>>n>>s;
    s=' '+s;
    for(int i = 1;i<=n;i++){
        int v = (s[i]=='R'?0:(s[i]=='G'?1:2));
        for(int j = 0;j<3;j++)others[j][i]=others[j][i-1];
        others[v][i]++;
        pos[v][++cnt[v]]=i;
    }
    for(int j = 0;j<=cnt[1];j++){
        for(int k = 0;k<=cnt[2];k++){
            for(int nxt = 0;nxt<3;nxt++){
                dp[0][j][k][nxt] = 1e9;
            }
        }
    }
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<=cnt[1];j++){
            for(int k = 0;k<=cnt[2];k++){
                for(int nxt = 0;nxt<3;nxt++){
                    dp[i&1^1][j][k][nxt] = 1e9;
                }
            }
        }
        for(int j = 0;j<=cnt[1]&&j<=i;j++){
            for(int k = 0;k<=cnt[2]&&j+k<=i;k++)if(i-j-k<=cnt[0]){
                for(int lst = 0;lst<3;lst++){
                    if(lst!=0&&i-j-k<cnt[0])chmin(dp[i&1^1][j][k][0],dp[i&1][j][k][lst] + cal(i-j-k,j,k,0));
                    if(lst!=1&&j<cnt[1])chmin(dp[i&1^1][j+1][k][1],dp[i&1][j][k][lst] + cal(i-j-k,j,k,1));
                    if(lst!=2&&k<cnt[2])chmin(dp[i&1^1][j][k+1][2],dp[i&1][j][k][lst] + cal(i-j-k,j,k,2));
                }
            }
        }
    }
    int ans = *min_element(dp[n&1][cnt[1]][cnt[2]],dp[n&1][cnt[1]][cnt[2]]+3);
    if(ans>n*n)cout<<"-1\n";
    else cout<<ans<<'\n';
}

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