Submission #1268652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268652		nerrrmin	Rice Hub (IOI11_ricehub)	C++20	100 / 100	11 ms	2396 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
long long n, l;
long long budget;
long long a[maxn];
long long pref[maxn];
long long recent = 0;
long long get_sum(int l, int r)
{
    return (pref[r] - pref[l-1]);
}
bool check(int pos, int expand)
{
    int lt = pos - expand;
    int rt = pos-1;
    long long onleft = get_sum(lt, rt);
    lt = pos+1;
    rt = pos + expand;
    long long onright = get_sum(lt, rt);
    long long curr = a[pos] * expand - onleft - a[pos] * expand + onright;
    recent = curr;
    return (recent <= budget);
}
int besthub(int R, int L, int X[], long long B)
{
    n = R;
    l = L;
    budget = B;
    for (int i = 1; i <= n; ++ i)
    {
        a[i] = X[i-1];
    }
    for (int i = 1; i <= n; ++ i)
        pref[i] = pref[i-1] + a[i];

    int best = 0;
    for (int i = 1; i <= n; ++ i)
    {
        int l = 0, r = min(1LL * i-1, (n - i)), mid, ans = 0;
        while(l <= r)
        {
            mid = (l + r)/2;
            if(check(i, mid))
            {
                l = mid + 1;
                ans = mid;
            }
            else r = mid - 1;
        }
        check(i, ans);
        best = max(best, ans * 2 + 1);
        int onleft = i - ans - 1;
        if(onleft > 0 && recent + a[i] - a[onleft] <= B)best = max(best, ans * 2+ 2);
        int onright = i + ans + 1;
        if(onright <= n && recent - a[i] + a[onright] <= B)best = max(best, ans * 2 + 2);
    }
  return best;
}

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