Submission #95096

#	Time	Username	Problem	Language	Result	Execution time	Memory
95096		Alexa2001	Rice Hub (IOI11_ricehub)	C++17	100 / 100	17 ms	3420 KiB

ricehub

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

using namespace std;

typedef long long ll;
const int Nmax = 1e5 + 5;

ll x[Nmax], s[Nmax], lim;
int n;

bool check(int nr)
{
    int i, m;
    ll curr;
    for(i=0; i<=n-nr; ++i)
    {
        m = (i + i + nr - 1) / 2;

        curr = (m - i + 1) * x[m] - (s[m] - s[i-1]);
        curr += (s[i+nr-1] - s[m]) - (i+nr-1 - m) * x[m];
        if(curr <= lim) return 1;
    }
    return 0;
}

int besthub(int R, int L, int X[], ll B)
{
    int st = 0, dr = R, mid, i;

    n = R; lim = B;
    for(i=0; i<n; ++i) x[i] = X[i], s[i] = s[i-1] + x[i];

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid)) st = mid+1;
            else dr = mid-1;
    }
    return dr;
}

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