Submission #476142

#	Time	Username	Problem	Language	Result	Execution time	Memory
476142		Blobo2_Blobo2	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	461 ms	757644 KiB

joi2019_ho_t3

/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
int dp[401][401][401][3],n;
vector<int>vy,vr,vg;
int tr[400],tg[400],ty[400];
int solve(int r=0,int g=0,int y=0,int last=0){
    //cout<<r<<' '<<g<<' '<<y<<' '<<last<<endl;
    int idx = r+g+y;
    if(idx==n)return 0;
    int &ret = dp[r][g][y][last];
    if(ret != -1)return ret;
    ret = 1e9;
    if(idx == 0){
        idx = vg[g];
        if(g+1<=tg[n-1])
            ret = min(ret,solve(r,g+1,y,1) + max(0,tr[idx] - r)+ max(0,ty[idx] - y) );
        idx = vy[y];
        if(y+1<=ty[n-1])
            ret = min(ret,solve(r,g,y+1,2) + max(0,tr[idx] - r)+ max(0,tg[idx] - g) );
        idx = vr[r];
        if(r+1<=tr[n-1])
            ret = min(ret,solve(r+1,g,y,0) + max(0,tg[idx] - g)+ max(0,ty[idx] - y) );
    }
    else if(last == 0){
        idx = vg[g];
        if(g+1<=tg[n-1])
            ret = min(ret,solve(r,g+1,y,1) + max(0,tr[idx] - r)+ max(0,ty[idx] - y));
        idx = vy[y];
        if(y+1<=ty[n-1])
            ret = min(ret,solve(r,g,y+1,2) + max(0,tr[idx] - r)+ max(0,tg[idx] - g) );
    }
    else if(last == 1){
        idx = vr[r];
        if(r+1<=tr[n-1])
            ret = min(ret,solve(r+1,g,y,0) + max(0,tg[idx] - g)+ max(0,ty[idx] - y) );
        idx = vy[y];
        if(y+1<=ty[n-1])
            ret = min(ret,solve(r,g,y+1,2) + max(0,tr[idx] - r)+ max(0,tg[idx] - g) );
    }
    else if(last == 2){
        idx = vg[g];
        if(g+1<=tg[n-1])
            ret = min(ret,solve(r,g+1,y,1) + max(0,tr[idx] - r)+ max(0,ty[idx] - y) );
        idx = vr[r];
        if(r+1<=tr[n-1])
            ret = min(ret,solve(r+1,g,y,0) + max(0,tg[idx] - g)+ max(0,ty[idx] - y) );
    }
    return ret;
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    n=nxt();
    string s;
    cin>>s;
    int arr[3];
    arr[0]=count(all(s),'R');
    arr[1]=count(all(s),'Y');
    arr[2]=count(all(s),'G');
    sort(arr,arr+3);
    int mn =0;
    if(arr[0]>arr[1]+1)mn += arr[0] - (arr[1]+1);
    if(arr[2]>arr[0]+arr[1]+1)mn+= arr[2] - (arr[0]+arr[1]+1);
    if(mn){
        cout<<-1<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        if(s[i] == 'R')
            vr.push_back(i),tr[i]++;
        if(s[i] == 'G')
            vg.push_back(i),tg[i]++;
        if(s[i] == 'Y')
            vy.push_back(i),ty[i]++;
        if(!i)continue;
        tr[i]+=tr[i-1];
        tg[i]+=tg[i-1];
        ty[i]+=ty[i-1];
    }
    memset(dp,-1,sizeof dp);
    cout<<solve();
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:21:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int mo=1e9+7,INF=1e18;
      |                        ^~~~

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