Submission #802052

#	Time	Username	Problem	Language	Result	Execution time	Memory
802052		Warinchai	Rice Hub (IOI11_ricehub)	C++14	0 / 100	247 ms	1064 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long sumf[100005];
long long sumb[100005];
long long n;
int am;
vector<long long>v;
long long cost;
pair<int,long long> tl(int i,int r,long long mx,long long left){
    int en=r;
    int st=0;
    int ans=r+1;
    //cout<<"mx:"<<mx<<endl;
    while(st<=en){
        int m=(st+en)/2;
        //cout<<"m:"<<m<<" "<<v[i]-v[m]<<" "<<sumb[m]-sumb[r+1]<<"-"<<(r-m+1)<<"*"<<n<<"-"<<v[r+1]<<endl;
        if(v[i]-v[m]<=mx&&(sumb[m]-sumb[r+1])-(r-m+1)*(n-v[r+1])<=left){
            ans=m;
            en=m-1;
        }else{
            st=m+1;
        }
    }
    //cout<<"r:"<<r<<endl;
    //cout<<ans<<":"<<left<<"-"<<"("<<sumb[ans]-sumb[r+1]<<"-"<<r+1-ans<<"*"<<n-v[r+1]<<")"<<endl;
    return {ans,left-((sumb[ans]-sumb[r+1])-(r+1-ans)*(n-v[r+1]))};
}
pair<int,long long> tr(int i,int l,long long mx,long long left){
    int en=am-1;
    int st=l;
    int ans=l-1;
    while(st<=en){
        int m=(st+en)/2;
        //cout<<"m:"<<m<<endl;
        //cout<<(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<<endl;
        if(v[m]-v[i]<=mx&&(sumf[m]-sumf[l-1])-(m-l+1)*(v[l-1])<=left){
            ans=m;
            st=m+1;
        }else{
            en=m-1;
        }
    }
    return {ans,left-((sumf[ans]-sumf[l-1])-(ans-l+1)*(v[l-1]))};
}
int cnl=0,cnr=0;
int fr(int i){
    //cout<<"I:"<<i<<endl;
    long long left=cost;
    //cout<<"left:"<<cost<<endl;
    int l=i+1,r=i-1;
    bool cl;
    if(i==0){
        cl=1;
    }else if(i==am-1){
        cl=0;
    }else{
        cl=v[i]-v[i-1]<v[i+1]-v[i];
    }
    cnl=0,cnr=0;
    //cout<<"right, left:"<<r<<" "<<l<<endl;
    while(left>=0){
        if(cl){
            //cout<<"going left"<<endl;
            long long mx;
            if(l<am){
                mx=v[l]-v[i];
            }else{
                mx=LLONG_MAX;
            }
            pair<int,int> move=tl(i,r,mx,left);
            left=move.second;
            //
            if(r==move.first-1){
                cnl=1;
            }
            r=move.first-1;
            //cout<<r<<" "<<left<<endl;
        }else{
            //cout<<"going right"<<endl;
            long long mx;
            if(r>=0){
                mx=v[i]-v[r];
            }else{
                mx=LLONG_MAX;
            }
            pair<int,int> move=tr(i,l,mx,left);
            left=move.second;
            if(l==move.first+1){
                cnr=1;
            }
            l=move.first+1;
            //cout<<l<<" "<<left<<endl;
        }
        //cout<<"result:"<<r<<" "<<l<<endl;
        if(cnl&&cnr){
            break;
        }
        cl^=1;
    }
    //cout<<"final result:"<<r<<" "<<l<<endl;
    //cout<<endl;
    return l-r-1;
}
int besthub(int r, int l, int x[], long long b)
{
    long long sum=0;
    cost=b;
    n=l;
    am=r;
    for(int i=0;i<r;i++){
        sum+=x[i];
        sumf[i]=sum;
        v.push_back(x[i]);
    }
    sum=0;
    for(int i=r-1;i>=0;i--){
        sum+=l-x[i];
        sumb[i]=sum;
    }
    /*cout<<"info:"<<endl;
    for(int i=0;i<r;i++){
        cout<<sumb[i]<<" ";
    }
    cout<<endl;*/
    int ans=0;
    for(int i=0;i<r;i++){
        ans=max(ans,fr(i));
    }
    return ans;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32