Submission #866344

#	Time	Username	Problem	Language	Result	Execution time	Memory
866344		yeediot	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1073 ms	18116 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=405;
const int inf=8e18;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s='X'+s;
    vector<int>v(n+1);
    vector<vector<int>>pre(3,vector<int>(n+1,0));
    vector<int>pos[3];
    pos[0].pb(-1);
    pos[1].pb(-1);
    pos[2].pb(-1);
    for(int i=1;i<=n;i++){
        if(s[i]=='Y'){
            v[i]=0;
        }
        else if(s[i]=='G'){
            v[i]=1;
        }
        else {
            v[i]=2;
        }
        pre[v[i]][i]=1;
        for(int j=0;j<3;j++){
            pre[j][i]+=pre[j][i-1];
        }
        pos[v[i]].pb(i);
    }
    vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(n+1,vector<int>(3,8e18)));
    dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;
    for(int i=1;i<=n;i++){
        vector<vector<vector<int>>>dp2(n+1,vector<vector<int>>(n+1,vector<int>(3,8e18)));
        for(int j=0;j<=min(i,pre[0][n]);j++){
            for(int k=0;k<=min(i-j,pre[1][n]);k++){
                if(i-j-k<0 or i-j-k>pre[2][n])continue;
                if(j){
                    dp2[j][k][0]=min(max(pos[0][j]-i,0LL)+min(dp[j-1][k][1],dp[j-1][k][2]),inf);
                }
                if(k){
                    dp2[j][k][1]=min(max(pos[1][k]-i,0LL)+min(dp[j][k-1][0],dp[j][k-1][2]),inf);
                }
                int r=i-j-k;
                if(r){
                    dp2[j][k][2]=min(max(pos[2][r]-i,0LL)+min(dp[j][k][0],dp[j][k][1]),inf);
                }
                //for(int h=0;h<3;h++)cout<<i<<' '<<j<<' '<<k<<' '<<r<<' '<<h<<' '<<dp2[j][k][h]<<'\n';
            }
        }swap(dp2,dp);
    }
    int ans=8e18;
    for(int i=0;i<3;i++){
        chmin(ans,dp[sz(pos[0])-1][sz(pos[1])-1][i]);
        //cout<<ans<<' ';
    }
    if(ans>=8e18){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans<<'\n';
    }
}
 /*
 input:
 dp[i][r][g][t]=dp[i-1][r-1][g]
 */

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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