Submission #742209

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742209	2023-05-15T19:43:10 Z	rainboy	Schools (IZhO13_school)	C	100 / 100	156 ms	8752 KB

school

#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

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]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	2 ms	360 KB	Output is correct
8	Correct	3 ms	340 KB	Output is correct
9	Correct	3 ms	340 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	3 ms	340 KB	Output is correct
12	Correct	3 ms	340 KB	Output is correct
13	Correct	23 ms	1220 KB	Output is correct
14	Correct	42 ms	2368 KB	Output is correct
15	Correct	70 ms	4636 KB	Output is correct
16	Correct	117 ms	5204 KB	Output is correct
17	Correct	118 ms	6472 KB	Output is correct
18	Correct	114 ms	7076 KB	Output is correct
19	Correct	132 ms	7564 KB	Output is correct
20	Correct	156 ms	8752 KB	Output is correct