Submission #1276911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276911		trandangquang	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	65 ms	57256 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=404;

int n,a[N],sum[3][N],pos[3][N],cpos[3];
string s;

int get(char c){
    if(c=='R')return 0;
    if(c=='G')return 1;
    if(c=='Y')return 2;
    return -1;
}

void solve(){
    cin>>n;
    cin>>s;

    rep(i,n) a[i+1]=get(s[i]);
//    foru(i,1,n)cout<<a[i]<<" ";
//    cout<<'\n';
    rep(i,3){
        foru(j,1,n){
            sum[i][j]=sum[i][j-1]+(a[j]==i);
            if(a[j]==i){
                pos[i][++cpos[i]]=j;
            }
        }
    }

    ll dp[cpos[0]+1][cpos[1]+1][cpos[2]+1][3];

    memset(dp,0x3f,sizeof(dp));
    dp[0][0][0][0]=0;

    foru(i,0,cpos[0]) foru(j,0,cpos[1]) foru(k,0,cpos[2]) foru(lst,0,2){
        if(i<cpos[0] && (i+j+k==0 || lst!=0)){
            int p=pos[0][i+1];
            mini(dp[i+1][j][k][0], dp[i][j][k][lst] +
                                   p + max(0,i-sum[0][p]) + max(0,j-sum[1][p]) + max(0,k-sum[2][p]) - (i+j+k+1));
        }

        if(j<cpos[1] && (i+j+k==0 || lst!=1)){
            int p=pos[1][j+1];
            mini(dp[i][j+1][k][1], dp[i][j][k][lst] +
                                   p + max(0,i-sum[0][p]) + max(0,j-sum[1][p]) + max(0,k-sum[2][p]) - (i+j+k+1));
        }

        if(k<cpos[2] && (i+j+k==0 || lst!=2)){
            int p=pos[2][k+1];
            mini(dp[i][j][k+1][2], dp[i][j][k][lst] +
                                   p + max(0,i-sum[0][p]) + max(0,j-sum[1][p]) + max(0,k-sum[2][p]) - (i+j+k+1));
        }
    }

    ll res=1e18;
    rep(i,3) mini(res, dp[cpos[0]][cpos[1]][cpos[2]][i]);//, cout<<i _ res<<'\n';
    if(res>1LL*n*(n-1)/2) cout<<"-1\n";
    else cout<<res<<'\n';
}

int32_t main(){
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    rep(i,tc){
        solve();
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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