CSES - HIIT Open 2018 - Results
 Task: Jobs Sender: Ukkonen Fan Club Submission time: 2018-05-26 13:53:48 Language: C++ Status: READY Result: ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.34 sdetails
#2ACCEPTED0.28 sdetails
#3ACCEPTED0.31 sdetails
#4ACCEPTED0.02 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.02 sdetails
#8ACCEPTED0.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 (ib < ind || ind < ia) return;
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: ACCEPTED

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

correct output
58819226961852

user output
58819226961852

#### 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: ACCEPTED

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

correct output
133340028532768

user output
133340028532768

#### 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: ACCEPTED

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

correct output
15

user output
15

#### Test 7

Verdict: ACCEPTED

input
2 0 3
3 1
1 1
2 1

correct output
5

user output
5

#### Test 8

Verdict: ACCEPTED

input
0 2 3
1 3
1 1
1 2

correct output
5

user output
5