Jobs

#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 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER