Submission #927947

#	Time	Username	Problem	Language	Result	Execution time	Memory
927947		TAhmed33	Rice Hub (IOI11_ricehub)	C++98	100 / 100	449 ms	10072 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool check (int n, int l, int x[], ll b, int mid) {
	map <ll, ll> tl, tr;
	ll sumtl = 0, sumtr = 0;
	ll cnttl = 0, cnttr = 0;
	ll mn = b + 1;
	for (ll i = 0; i < mid; i++) {
		sumtr += x[i]; tr[x[i]]++;
		cnttr++;
	}
	while (cnttr >= cnttl) {
		auto y = tr.begin();
		ll z = (*y).first;
		tr[z]--;
		if (tr[z] == 0) tr.erase(z);
		tl[z]++;
		sumtr -= z;
		sumtl += z;
		cnttr--;
		cnttl++;
	}
	auto mm = tl.end();
	mm--;
	mn = min(mn, ((*mm).first) * cnttl - sumtl + sumtr - ((*mm).first) * cnttr);
	for (ll i = mid; i < n; i++) {
		if (tl.count(x[i - mid])) {
			tl[x[i - mid]]--;
			if (tl[x[i - mid]] == 0) tl.erase(x[i - mid]);
			sumtl -= x[i - mid];
			cnttl--;
			sumtr += x[i];
			tr[x[i]]++;
			cnttr++;
		} else {
			tr[x[i - mid]]--;
			if (tr[x[i - mid]] == 0) tr.erase(x[i - mid]);
			sumtr -= x[i - mid];
			cnttr--;
			sumtl += x[i];
			tl[x[i]]++;
			cnttl++;
		}
		while (cnttl >= cnttr) {
			auto z = tl.end();
			z--;
			ll j = (*z).first;
			tl[j]--;
			if (tl[j] == 0) tl.erase(j);
			tr[j]++;
			sumtl -= j;
			sumtr += j;
			cnttl--;
			cnttr++;
		}
		while (cnttr >= cnttl) {
			auto z = tr.begin();
			ll j = (*z).first;
			tr[j]--;
			if (tr[j] == 0) tr.erase(j);
			tl[j]++;
			sumtr -= j;
			sumtl += j;
			cnttr--;
			cnttl++;
		}
		auto mm = tl.end();
		mm--;
		mn = min(mn, ((*mm).first) * cnttl - sumtl + sumtr - ((*mm).first) * cnttr);
	}
	return (mn <= b);
}
int besthub (int n, int l2, int x[], ll b) {
	int l = 0, r = n;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(n, l2, x, b, mid)) {
			l = mid + 1; ans = mid;
		} else {
			r = mid - 1;
		}
	}
	return ans;
}

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