Submission #163183

#	Time	Username	Problem	Language	Result	Execution time	Memory
163183		kostia244	Rice Hub (IOI11_ricehub)	C++17	100 / 100	51 ms	6520 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll sumlo = 0, sumhi = 0;
multiset<ll> lo, hi;
ll eval() {
	ll med = *lo.rbegin();
	return (lo.size() * med - sumlo) + (sumhi - hi.size() * med);
}
void balance() {
	while (lo.size() < hi.size()) {
		sumhi -= *hi.begin();
		sumlo += *hi.begin();
		lo.insert(*hi.begin());
		hi.erase(hi.begin());
	}
}
void pop() {
	sumlo -= *lo.begin();
	lo.erase(lo.begin());
	balance();
}
void push(ll x) {
	hi.insert(x);
	sumhi += x;
	balance();
}
int besthub(int R, int L, int X[], long long B) {
	ll ans = 0;
	for(int i = 0; i < R; i++) {
		push(X[i]);
		while(eval()>B) pop();
		ans = max(ans, (ll)lo.size()+(ll)hi.size());
	}
	return ans;
}

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