제출 #239560

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

ricehub

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

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

    for (int i = 1; i<R; i++)
    {
        int len = X[i+1]-X[i];
        if (len > B) continue;
        int lo = 0, hi = min(i-1,R-i-1)+1;
        while(lo+1 < hi)
        {
            int d = (lo+hi)/2;
            long long lsum = range_sum(i-d, i-1, i);
            long long rsum = range_sum(i+2, i+d+1, i);
            if (lsum+rsum+len <= B)
                lo = d;
            else 
                hi = d;
        }
        long long 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