Submission #866353

#	Time	Username	Problem	Language	Result	Execution time	Memory
866353		yeediot	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	348 ms	18264 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=1e12;
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]=='R'){
            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,1e12)));
    vector<vector<vector<int>>>dp2(n+1,vector<vector<int>>(n+1,vector<int>(3,1e12)));
    dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;
    for(int i=1;i<=n;i++){
        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;
                int r=i-j-k;
                if(j)dp2[j][k][0]=min(max(pre[1][pos[0][j]]-k,0LL)+max(pre[2][pos[0][j]]-r,0LL)+min(dp[j-1][k][1],dp[j-1][k][2]),inf);
                if(k)dp2[j][k][1]=min(max(pre[0][pos[1][k]]-j,0LL)+max(pre[2][pos[1][k]]-r,0LL)+max(pos[1][k]-i,0LL)+min(dp[j][k-1][0],dp[j][k-1][2]),inf);
                if(r)dp2[j][k][2]=min(max(pre[0][pos[2][r]]-j,0LL)+max(pre[1][pos[2][r]]-k,0LL)+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';
            }
        }
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                for(int g=0;g<3;g++){
                    dp[j][k][g]=dp2[j][k][g];
                    dp2[j][k][g]=inf;
                }
            }
        }
    }
    int ans=1e12;
    for(int i=0;i<3;i++){
        chmin(ans,dp[sz(pos[0])-1][sz(pos[1])-1][i]);
    }
    if(ans>=1e12){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans/2<<'\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