Submission #421842

#	Time	Username	Problem	Language	Result	Execution time	Memory
421842		arayi	Rice Hub (IOI11_ricehub)	C++17	100 / 100	220 ms	2524 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#define lli long long
using namespace std;

const int N = 1e6 + 30;
int n;
lli pr[N];
lli s(int l, int r)
{
    lli ret = pr[r];
    if(l) ret -= pr[l-1];
    return ret;
}
int besthub(int N, int L, int X[], long long B)
{
    n = N;
    for (int i = 0; i < n; i++)
    {
        pr[i] = X[i];
        if(i) pr[i] += pr[i - 1];
    }
    int ret = 0;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = i, ans = 0;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            lli sm = (lli)mid * 1LL * X[i] - s(i - mid, i - 1);
            int l1 = 0, r1 = n - i - 1, ans1 = 0;
            while(l1 <= r1)
            {
                int md = (l1 + r1) / 2;
                lli ss = -(lli)md * 1LL * X[i] + s(i + 1, i + md);
                if(sm + ss <= B) l1 = md + 1, ans1 = md;
                else r1 = md - 1;
            }
            if(sm <= B && (i + ans1 == n - 1 || X[i + ans1 + 1] - X[i] >= X[i] - X[i - mid])) l = mid + 1, ans = mid;
            else r = mid - 1;
            ret = max(ret, ans + ans1 + 1);
        }
        //cout << ans << " ";
        l = 0, r = n - i - 1, ans = 0;
        while(l <= r)
        {
            int mid = (l + r) / 2;
            lli sm = -(lli)mid * 1LL * X[i] + s(i + 1, i + mid);
            int l1 = 0, r1 = i, ans1 = 0;
            while(l1 <= r1)
            {
                int md = (l1 + r1) / 2;
                lli ss = (lli)md * 1LL * X[i] - s(i - md, i - 1);
                if(sm + ss <= B) l1 = md + 1, ans1 = md;
                else r1 = md - 1;
            }
            if(sm <= B && (i - ans1 == 0 || X[i] - X[i - ans1 - 1] >= X[i + mid] - X[i])) l = mid + 1, ans = mid;
            else r = mid - 1;
            ret = max(ret, ans + ans1 + 1);
        }
        //cout << ans << endl;
    }
    return ret;
}

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