Submission #241190

#	Time	Username	Problem	Language	Result	Execution time	Memory
241190		gratus907	Rice Hub (IOI11_ricehub)	C++17	0 / 100	40 ms	3328 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll RR, LL, BB;

ll crop[101010];
ll presum[101010];
ll curbest = 0, curans = 0;
inline ll range_sum(ll Left, ll Right, ll Target)
{
    if (Left <= 0 || Right<=0 || Right>RR || Left>RR) return LLONG_MAX;
    ll tmp = presum[Right]-presum[Left-1];
    return abs(tmp - crop[Target]*(Right-Left+1));
}
int besthub(int R, int L, int X[], long long B)
{
    RR = R; LL = L; BB = B;
    for (ll i = 1; i<=RR; i++)
    {
        crop[i] = X[i];
        presum[i] = presum[i-1]+crop[i];
    }
    for (ll i = 1; i<=RR; i++)
    {
        ll lo = 0, hi = min(i-1,RR-i)+1;
        while(lo+1 < hi)
        {
            ll d = (lo+hi)/2;
            ll lsum = range_sum(i-d, i-1, i);
            ll rsum = range_sum(i+1, i+d, i);
            if (lsum+rsum <= BB)
                lo = d;
            else 
                hi = d;
        }
        ll possible_gets = 2*lo+1;
        if (possible_gets>=curbest)
        {
            curbest = possible_gets;
            curans = i;
        }
    }

    for (ll i = 1; i<RR; i++)
    {
        ll len = crop[i+1]-crop[i];
        if (len > BB) continue;
        ll lo = 0, hi = min(i-1,RR-i-1)+1;
        while(lo+1 < hi)
        {
            ll d = (lo+hi)/2;
            ll lsum = range_sum(i-d, i-1, i);
            ll rsum = range_sum(i+2, i+d+1, i);
            if (lsum+rsum+len <= BB)
                lo = d;
            else 
                hi = d;
        }
        ll possible_gets = 2*lo+2;
        if (possible_gets>=curbest)
        {
            curbest = possible_gets;
            curans = i;
        }
    }
    return curbest;
}

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