Submission #307681

#	Time	Username	Problem	Language	Result	Execution time	Memory
307681		juggernaut	Rice Hub (IOI11_ricehub)	C++14	68 / 100	22 ms	2816 KiB

ricehub

#include"ricehub.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[100005];
ll b,pref[100005],suff[100005];
ll pref_calc(ll l,ll r){
    return pref[r]-(l-1)*(a[r]-a[l-1])-pref[l-1];
}
ll suff_calc(ll l,ll r){
    return suff[l]-(n-r)*(a[r+1]-a[l])-suff[r+1];
}
bool app(ll l,ll r){
    ll i=(l+r)>>1;
    ll mn=pref_calc(l,i)+suff_calc(i,r);
    return mn<=b;
}
bool check(int x){
    bool flag=0;
    for(int i=1;i+x-1<=n;i++)flag|=app(i,x+i-1);
    return flag;
}
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=n,m;
    while(l<r){
        m=(l+r+1)>>1;
        if(check(m))l=m;
        else r=m-1;
    }
    return l;
}
//#include"grader.cpp"

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