about summary refs log tree commit diff
path: root/2ndary/12/QG-2014/minroad.c
blob: d4bc129b348aeef0bc5c826dd2561210d59e7a2b (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdlib.h>
#include <stdio.h>

struct trees {
	long d, a, b;
};

int cmp(const void *x, const void *y)
{
	long d = ((struct trees *) x)->d - ((struct trees *) y)->d;
	if (d < 0)
		return -1;
	else if (d > 0)
		return 1;
	else
		return 0;
}

int main()
{
	FILE *f = fopen("MINROAD.INP", "r");
	long n, a, b;
	fscanf(f, "%ld %ld %ld\n", &n, &a, &b);

	struct trees *t = (struct trees *) malloc(n * sizeof(struct trees));
	long k;
	for (long i = 0; i < n; i++) {
		fscanf(f, "%ld %ld\n", &t[i].d, &k);
		if (k == 1) {
			t[i].a = 1;
			t[i].b = 0;
		} else {
			t[i].a = 0;
			t[i].b = 1;
		}
	}
	fclose(f);

	qsort(t, n, sizeof(struct trees), cmp);
	for (long i = 1; i < n; i++) {
		t[i].a += t[i - 1].a;
		t[i].b += t[i - 1].b;
	}

	struct trees *enough = t;
	for (k = n; k > 0 && (enough->a < a || enough->b < b); k--)
		enough++;

	long d0 = -1, d1, maxa, maxb;
	for (; k--; enough++) {
		maxa = enough->a - a;
		maxb = enough->b - b;
		while (t->a <= maxa && t->b <= maxb) {
			t++;
			n--;
		}

		d1 = d0;
		d0 = enough->d - t->d;
		if (d1 != -1 && d1 < d0)
			d0 = d1;
	}

	f = fopen("MINROAD.OUT", "w");
	fprintf(f, "%ld\n", d0);
	fclose(f);

	return 0;
}