제출 #956968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956968		Nelt	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	17 ms	4444 KiB

ricehub

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

#define ll long long
#define endl "\n"
using namespace std;

int besthub(int n, int L, int x[], long long B)
{
    ll ans = 0, pref[n];
    for (ll i = 0; i < n; i++)
        pref[i] = (i - 1 >= 0 ? pref[i - 1] : 0) + x[i];
    auto sum = [&](ll l, ll r)
    {
        return pref[r] - (l - 1 >= 0 ? pref[l - 1] : 0);
    };
    auto best = [&](ll l, ll r)
    {
        ll lo = l, hi = r - 1, mid, ans = x[r] * (r - l + 1) - sum(l, r);
        while (lo <= hi)
        {
            mid = (lo + hi) >> 1;
            ans = min({ans, x[mid] * (mid - l + 1) - x[mid] * (r - mid) + sum(mid + 1, r) - sum(l, mid), x[mid + 1] * (mid + 1 - l + 1) - x[mid + 1] * (r - (mid + 1)) + sum(mid + 2, r) - sum(l, mid + 1)});
            if (x[mid] * (mid - l + 1) - x[mid] * (r - mid) + sum(mid + 1, r) - sum(l, mid) < x[mid + 1] * (mid + 1 - l + 1) - x[mid + 1] * (r - (mid + 1)) + sum(mid + 2, r) - sum(l, mid + 1))
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return ans;
    };
    for (ll i = 0, j = 0; i < n; i++)
    {
        while (best(j, i) > B)
            j++;
        ans = max(ans, i - j + 1);
    }
    return ans;
}

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