CSES - HIIT Open 2018 - Results
Submission details
Task:Jobs
Sender:Ukkonen Fan Club
Submission time:2018-05-26 13:39:38 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1--details
#2ACCEPTED0.29 sdetails
#3--details
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#60.01 sdetails
#7ACCEPTED0.01 sdetails
#80.01 sdetails

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

const int N = 2 * (int)1e5;
int as[N];
int bs[N];
int vals[N];
int ind[N];
int used[N];
int b;
int h = 1;

long long sum[4 * N];
int cou[4 * N];

long long getKLast(int i, int k) {
	if (cou[i] == k) return sum[i];
	int left = 2 * i;
	int right = 2 * i + 1;
	if (cou[right] >= k) return getKLast(right, k);
	return sum[right] + getKLast(left, k - cou[right]);
}

void update(int i) {
	int left = 2 * i;
	int right = 2 * i + 1;
	sum[i] = sum[left] + sum[right];
	cou[i] = cou[left] + cou[right];
}

void set(int ind, int v, int i = 1, int ia = 0, int ib = h - 1) {
	if (ia == ib) {
		cou[i] = v;
		if (cou[i]) {
			sum[i] = vals[ind];
		} else {
			sum[i] = 0;
		}
	} else {
		int mid = (ia + ib) >> 1;
		set(ind, v, 2 * i, ia, mid);
		set(ind, v, 2 * i + 1, mid + 1, ib);
		update(i);
	}
}

long long mins() {
	return getKLast(1, b);
}

int main() {
	int a, n;
	std::cin >> a >> b >> n;
	while(h < n) h <<= 1;

	std::vector<std::pair<int, int>> ord;
	std::vector<std::pair<int, int>> best_a;
	std::vector<std::pair<int, int>> best_b;
	for (int i = 0; i < n; ++i) {
		int va, vb;
		std::cin >> va >> vb;
		ord.push_back({vb - va, i});
		best_a.push_back({-va, i});
		best_b.push_back({-vb, i});
		as[i] = va;
		bs[i] = vb;
	}
	sort(ord.begin(), ord.end());
	sort(best_a.begin(), best_a.end());
	sort(best_b.begin(), best_b.end());
	
	for (int i = 0; i < n; ++i) {
		vals[i] = ord[i].first;
		ind[ord[i].second] = i;
	}
	
	int ab = a + b;
	long long sum = 0;
	for (int j = 0; j < ab; ++j) {
		int i = best_a[j].second;
		used[i] = 1;
		set(ind[i], 1);
		sum += as[i];
	}
	long long res = sum + mins();
	int ia = ab;
	int ib = 0;
	while(ib < ab - 1) {
		while(ia > 0) {
			--ia;
			int i = best_a[ia].second;
			--used[i];
			if (used[i] == 0) {
				sum -= as[i];
				set(ind[i], 0);
				break;
			}
			if (ia == 0) {
				ia = -1;
				break;
			}
		}
		if (ia == -1) break;
		
		while(ib < ab) {
			int i = best_b[ib].second;
			++ib;
			++used[i];
			if (used[i] == 1) {
				sum += as[i];
				set(ind[i], 1);
				break;
			}
			if (ib == ab) {
				ib = -1;
				break;
			}
		}
		if (ib == -1) break;

		res = std::max(res, sum + mins());
	}
	std::cout << res << '\n';
}

Test details

Test 1

Verdict:

input
12345 54321 200000
159509898 981869288
727914829 812494607
382740364 106927167
291351532 356889470
...

correct output
58819226961852

user output
(empty)

Test 2

Verdict: ACCEPTED

input
1 1 200000
664293393 446126294
303053683 177744194
130410611 450516458
645484148 777139798
...

correct output
1999991597

user output
1999991597

Test 3

Verdict:

input
100000 100000 200000
597408010 262805535
561239330 95992085
690324270 432159964
892983528 703183828
...

correct output
133340028532768

user output
(empty)

Test 4

Verdict: ACCEPTED

input
0 0 1
1 1

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

input
5 0 5
1 10
2 10
3 10
4 10
...

correct output
15

user output
15

Test 6

Verdict:

input
0 5 5
10 1
10 2
10 3
10 4
...

correct output
15

user output
25

Test 7

Verdict: ACCEPTED

input
2 0 3
3 1
1 1
2 1

correct output
5

user output
5

Test 8

Verdict:

input
0 2 3
1 3
1 1
1 2

correct output
5

user output
4