# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
742209 | rainboy | Schools (IZhO13_school) | C11 | 156 ms | 8752 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <string.h>
#define N 300000
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N], bb[N], iia[N], iib[N], n, k;
int *xx;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] > xx[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long long x; int ka;
void solve(int c) {
static char used[N];
int h, i, j, ia, ib;
memset(used, 0, n * sizeof *used);
i = 0, j = 0, x = 0, ka = 0;
for (h = 0; h < k; h++) {
while (used[iia[i]])
i++;
while (used[iib[j]])
j++;
ia = iia[i], ib = iib[j];
if (aa[ia] - c > bb[ib])
used[ia] = 1, x += aa[ia] - c, ka++;
else
used[ib] = 1, x += bb[ib];
}
}
int main() {
int ka_, kb_, i, lower, upper, c;
scanf("%d%d%d", &n, &ka_, &kb_), k = ka_ + kb_;
for (i = 0; i < n; i++)
scanf("%d%d", &aa[i], &bb[i]);
for (i = 0; i < n; i++)
iia[i] = i;
xx = aa, sort(iia, 0, n);
for (i = 0; i < n; i++)
iib[i] = i;
xx = bb, sort(iib, 0, n);
lower = -INF, upper = INF;
while (upper - lower > 1) {
c = (lower + upper) / 2;
solve(c);
if (ka <= ka_)
upper = c;
else
lower = c;
}
solve(upper);
printf("%lld\n", x + (long long) upper * ka_);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |