Submission #1139289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139289		Warinchai	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	320 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long pre[100005];
long long suf[100005];
int n;
/*struct segtree{
    struct node{
        int mx,sum;
        node(int x=0){
            mx=sum=x;
        }
        friend node operator+(node a,node b){
            node c;
            c.mx=max(a.mx,b.mx);
            c.sum=a.sum+b.sum;
            return c;
        }
    };
    node info[400006];
    void buildp(int st,int en,int i){
        if(st==en)return void(info[i]=pre[st]);
        int m=(st+en)/2;
        buildp(st,m,i*2);
        buildp(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
    void builds(int st,int en,int i){
        if(st==en)return void(info[i]=suf[st]);
        int m=(st+en)/2;
        builds(st,m,i*2);
        builds(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
    pair<int,node> f(int st,int en,int i,int l,int r,int k,int b){
        if(st>r||en<l)return {-1,node()};
        if(st>=l&&en<=r)return {,info[i]};
        int m=(st+en)/2;
        auto x=f(st,m,i*2,l,r,k,b);
        if(x.first==0)
    }
}*/
long long ar[100005];
long long cost(int m){
    long long ans=LLONG_MAX;
    for(int i=1;i+m-1<=n;i++){
        int l=i,r=i+m-1;
        int md=(l+r)/2;
        long long cst=pre[r]-pre[md-1]-ar[md]*(r-md+1) + suf[l]-suf[md+1]-ar[md]*(md-l+1);
        ans=min(ans,cst);
    }
    return ans;
}
int besthub(int R, int L, int X[], long long B)
{
    n=R;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+X[i-1];
        //cerr<<pre[i]<<" ";
    }
    //cerr<<"\n";
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1]+L-X[i-1];
        //cerr<<suf[i]<<" ";
    }
    //cerr<<"\n";
    for(int i=1;i<=n;i++)ar[i]=X[i-1];
    int st=1,en=R,ans=0;
    while(st<=en){
        int m=(st+en)/2;
        long long x=cost(m);
        //cerr<<m<<" "<<x<<"\n";
        if(x<=B){
            st=m+1;
            ans=m;
        }else{
            en=m-1;
        }
    }
    return ans;
}

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