제출 #1124172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124172		njoop	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	2376 KiB

ricehub

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

int n;
vector<ll> arr, pre;

ll cost(ll k) {
    ll mnco = 1e18;
    for(int i=1; i<=n-k+1; i++) {
        ll left = (arr[i+(k/2)]*(k/2+1))-(pre[i+(k/2)]-pre[i-1]);
        ll right = (pre[i+k-1]-pre[i+(k/2)])-(arr[i+(k/2)]*(k-(k/2)-1));
        mnco = min(mnco, left+right);
    }
    return mnco;
}

int besthub(int R, int L, int X[], long long B) {
    n=R;
    arr.assign(R+10, 0);
    pre.assign(R+10, 0);
    for(int i=1; i<=R; i++) {
        arr[i] = X[i-1];
        pre[i] = pre[i-1] + arr[i];
    }
    ll l=1, r=R+1;
    while(l < r) {
        ll mid = (l+r)/2;
        if(cost(mid) > B) {
            r = mid;
        } else {
            l = mid+1;
        }
    }
    return l-1;
}

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