Submission #460705

#	Time	Username	Problem	Language	Result	Execution time	Memory
460705		BT21tata	Rice Hub (IOI11_ricehub)	C++17	68 / 100	16 ms	3276 KiB

ricehub

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

typedef long long ll;

using namespace std;

ll cnt[100005], a[100005];

int check(int x, int n)
{
    int lnum=x>>1;
    int rnum=x-lnum-1;
    ll ans=0, cur, ret=1e18;
    for(int i=lnum; i<n-rnum; i++)
    {
        cur=cnt[i]-cnt[i-lnum];
        ans=lnum*a[i]-cur;

        cur=cnt[i+rnum+1]-cnt[i+1];
        ans+=(cur-rnum*a[i]);

        ret=min(ans, ret);
    }
    return ret;
}

int besthub(int n, int len, int X[], long long m)
{
    for(int i=0; i<n; i++)
        cnt[i+1]=cnt[i]+X[i], a[i]=X[i];

    int l=0, r=n, mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
    //    cout<<l<<' ' <<r<<' '<<mid<<' '<<check(mid, n)<<endl;
        if(check(mid, n)<=m) l=mid+1;
        else r=mid-1;
    }
    return r;
}

/*


5 20 6
1 2 10 12 14
3

*/

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