Submission #735092

#	Time	Username	Problem	Language	Result	Execution time	Memory
735092		tigar	Rice Hub (IOI11_ricehub)	C++14	100 / 100	17 ms	2380 KiB

ricehub

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

using namespace std;
typedef long long ll;
ll prefs[100010];

ll cost(ll l, ll r, int *x)
{
    ll m=(l+r)/2;
    return prefs[r+1]-prefs[m+1]-(r-m)*x[m]-prefs[m]+prefs[l]+(m-l)*x[m];
}

int besthub(int R, int L, int *X, ll B)
{
    prefs[0]=0;
    for(int i=1; i<=R; i++)prefs[i]=prefs[i-1]+X[i-1];
    ll k=0, ans=0;
    for(ll i=0; i<R; i++)
    {
        while(cost(k, i, X)>B and k<=i)k++;
        //cout<<cost(k, i, X)<<endl;;
        ans=max(i-k+1, ans);
    }
    //cout <<cost(0, 4, X)<<endl;
    return ans;
}

/*int main()
{
    int r, l, x[100010];
    ll b;
    cin>>r>>l>>b;
    for(int i=0; i<r; i++)cin>>x[i];
    //cin>>b;
    cout<<besthub(r, l, x, b);
    return 0;
}*/

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