Submission #738868

#	Time	Username	Problem	Language	Result	Execution time	Memory
738868		ETheBest3	Rice Hub (IOI11_ricehub)	C++14	17 / 100	18 ms	2508 KiB

ricehub

#include "ricehub.h"
#define lli long long
const lli MAXN=100005;
lli pref[MAXN];
int besthub(int R, int L, int X[], long long B)
{
    for(lli i=0; i<R; i++)
    {
        if(i==0)pref[i]=X[i];
        else pref[i]=pref[i-1]+X[i];
    }
    lli p1=0, p2=0, p3=0, now=0, sum=0, ans=0;
    for(p1=-1; p1<R; p1++)
    {
        if(p2<p1+1)p2=p1+1;
        for(; p2<R; p2++)
        {
            if(p1!=-1)now=(pref[p2]-pref[p1])/(p2-p1);
            else now=pref[p2]/(p2+1);
            while(p3<p2 and X[p3+1]<=now)p3++;
            if(p1!=-1)sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3-p1)-(pref[p3]-pref[p1]);
            else sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3+1)-pref[p3];
            if(sum>B)break;
        }
        if(ans<p2-p1-1)ans=p2-p1-1;
        p2--;
    }
    return ans;
}

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