Submission #1124148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124148		njoop	Rice Hub (IOI11_ricehub)	C++17	17 / 100	0 ms	328 KiB

ricehub

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

int n;
vector<int> arr;

ll cost(int k) {
    multiset<ll> s1, s2;
    ll mnco = 1e18, su1=0, su2=0, mxl=0, mnr=0, med=0;
    for(int i=1; i<=n; i++) {
        if(i > k) {
            if(s1.find(arr[i-k]) != s1.end()) {
                s1.erase(s1.find(arr[i-k]));
                su1 -= arr[i-k];
            } else {
                s2.erase(s2.find(arr[i-k]));
                su2 -= arr[i-k];
            }
        }
        if(s1.size() <= s2.size()) {
            s1.insert(arr[i]);
            su1 += arr[i];
        } else {
            s2.insert(arr[i]);
            su2 += arr[i];
        }
        if(s1.size() && s2.size() && *s1.rbegin() > *s2.begin()) {
            mxl = *s1.rbegin();
            mnr = *s2.begin();
            su1 += mnr - mxl;
            su2 += mxl - mnr;
            s1.insert(mnr);
            s1.erase(s1.find(mxl));
            s2.insert(mxl);
            s2.erase(s2.find(mnr));
        }
        if(i > k-1) {
            med = *s1.rbegin();
            ll co = s1.size()*med - su1 + su2 - s2.size()*med;
            mnco = min(mnco, co);
        }
    }
    return mnco;
}

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

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