Submission #742209

#TimeUsernameProblemLanguageResultExecution timeMemory
742209rainboySchools (IZhO13_school)C11
100 / 100
156 ms8752 KiB
#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)

school.c: In function 'main':
school.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d%d%d", &n, &ka_, &kb_), k = ka_ + kb_;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &aa[i], &bb[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...