oj.uz

Submission #927947

# Submission time Handle Problem Language Result Execution time Memory
927947 2024-02-15T14:28:31 Z TAhmed33 Rice Hub (IOI11_ricehub) C++
100 / 100
 449 ms 10072 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 448 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 448 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 500 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 452 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 444 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 2 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2 ms 348 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 3 ms 348 KB Output is correct
22 Correct 3 ms 348 KB Output is correct
23 Correct 8 ms 604 KB Output is correct
24 Correct 8 ms 604 KB Output is correct
25 Correct 9 ms 780 KB Output is correct
26 Correct 9 ms 600 KB Output is correct
27 Correct 12 ms 736 KB Output is correct
28 Correct 12 ms 600 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1260 KB Output is correct
2 Correct 77 ms 1260 KB Output is correct
3 Correct 428 ms 9920 KB Output is correct
4 Correct 430 ms 10036 KB Output is correct
5 Correct 32 ms 2908 KB Output is correct
6 Correct 30 ms 2908 KB Output is correct
7 Correct 90 ms 3668 KB Output is correct
8 Correct 90 ms 3688 KB Output is correct
9 Correct 114 ms 3160 KB Output is correct
10 Correct 117 ms 3160 KB Output is correct
11 Correct 449 ms 10072 KB Output is correct
12 Correct 441 ms 9772 KB Output is correct
13 Correct 214 ms 4572 KB Output is correct
14 Correct 205 ms 4556 KB Output is correct
15 Correct 289 ms 8016 KB Output is correct
16 Correct 317 ms 8528 KB Output is correct
17 Correct 330 ms 9168 KB Output is correct
18 Correct 331 ms 8948 KB Output is correct
19 Correct 419 ms 9576 KB Output is correct
20 Correct 417 ms 9580 KB Output is correct