Submission #735073

#	Time	Username	Problem	Language	Result	Execution time	Memory
735073		tigar	Rice Hub (IOI11_ricehub)	C++14	0 / 100	12 ms	2512 KiB

ricehub

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

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

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

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

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

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