Submission #594343

#	Time	Username	Problem	Language	Result	Execution time	Memory
594343		Bench0310	Rice Hub (IOI11_ricehub)	C++17	100 / 100	27 ms	1492 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;
typedef long long ll;

int besthub(int n,int L,int pos[],ll b)
{
    vector<ll> sum(n,0);
    for(int i=0;i<n;i++) sum[i]=(i>0?sum[i-1]:0)+pos[i];
    auto s=[&](int l,int r){return ((r>=0?sum[r]:0)-(l>0?sum[l-1]:0));};
    int res=0;
    for(int i=0;i<n;i++)
    {
        int l=0,r=n;
        while(l<r-1)
        {
            int m=(l+r)/2;
            int cl=m/2;
            int cr=(m+1)/2;
            int x=i-cl;
            int y=i+cr;
            bool ok=0;
            if(0<=x&&y<n) ok=(cl*ll(pos[i])-s(x,i-1)+s(i+1,y)-cr*ll(pos[i])<=b);
            if(ok) l=m;
            else r=m;
        }
        res=max(res,l+1);
    }
    return res;
}

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