Submission #308204

#	Time	Username	Problem	Language	Result	Execution time	Memory
308204		juggernaut	Rice Hub (IOI11_ricehub)	C++14	0 / 100	3 ms	896 KiB

ricehub

#include"ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[100005];
ll b,pref[100005],suff[100005];
ll pref_calc(ll l,ll r){
    return pref[r]-1ll*(l-1)*(a[r]-a[l-1])-pref[l-1];
}
ll suff_calc(ll l,ll r){
    return suff[l]-1ll*(n-r)*(a[r+1]-a[l])-suff[r+1];
}
bool app(ll l,ll r){
    ll i=(l+r)>>1ll;
    ll mn=pref_calc(l,i)+suff_calc(i,r);
    return mn<=b;
}
int besthub(int N,int L,int A[],ll B){
    n=N;b=B;
    for(int i=0;i<n;i++)a[i+1]=A[i];
    for(int i=1;i<=n;i++)
        pref[i]=pref[i-1]+(i-1)*(a[i]-a[i-1]);
    for(int i=n;i>=1;i--)
        suff[i]=suff[i+1]+(n-i)*(a[i+1]-a[i]);
    int l=1,r=1,mx=1;
    while(r<=n){
        r++;
        while(!app(l,r))l++;
        mx=max(mx,r-l+1);
    }
    return mx;
}
//#include"grader.cpp"

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