#include <stdio.h>
#define N 200000
#define M 200000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
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;
}
}
int main() {
static int aa[N], kk[N], bb[M], ll[M], ii[N], jj[M];
int n, m, i, j;
long long a, k, b, l, sum;
scanf("%d", &n);
k = 0, sum = 0;
for (i = 0; i < n; i++) {
scanf("%d%d", &aa[i], &kk[i]);
k += kk[i], sum += (long long) aa[i] * kk[i];
ii[i] = i;
}
xx = aa, sort(ii, 0, n);
scanf("%d", &m);
b = 0;
for (j = 0; j < m; j++) {
scanf("%d%d", &bb[j], &ll[j]);
b += (long long) bb[j] * ll[j];
jj[j] = j;
}
xx = bb, sort(jj, 0, m);
a = 0, l = 0, j = m - 1;
while (j >= 0 && bb[jj[j]] >= k) {
b -= (long long) bb[jj[j]] * ll[jj[j]], l += ll[jj[j]];
j--;
}
if (a + b < sum && k <= (sum - 1 - a - b) / l) {
printf("0\n");
return 0;
}
for (i = 0; i < n; i++) {
a += (long long) aa[ii[i]] * kk[ii[i]], k -= kk[ii[i]];
while (j >= 0 && bb[jj[j]] >= k) {
b -= (long long) bb[jj[j]] * ll[jj[j]], l += ll[jj[j]];
j--;
}
if (a + b < sum && k <= (sum - 1 - a - b) / l) {
printf("0\n");
return 0;
}
}
printf("1\n");
return 0;
}
Compilation message
bodyguards.c: In function 'main':
bodyguards.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
bodyguards.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf("%d%d", &aa[i], &kk[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
bodyguards.c:49:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | scanf("%d%d", &bb[j], &ll[j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
292 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
292 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
292 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
0 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
296 KB |
Output is correct |
17 |
Correct |
0 ms |
292 KB |
Output is correct |
18 |
Correct |
1 ms |
292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
292 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
296 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
308 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
288 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
292 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
560 KB |
Output is correct |
2 |
Correct |
2 ms |
436 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
436 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
532 KB |
Output is correct |
7 |
Correct |
3 ms |
468 KB |
Output is correct |
8 |
Correct |
4 ms |
436 KB |
Output is correct |
9 |
Correct |
4 ms |
556 KB |
Output is correct |
10 |
Correct |
4 ms |
564 KB |
Output is correct |
11 |
Correct |
3 ms |
468 KB |
Output is correct |
12 |
Correct |
3 ms |
468 KB |
Output is correct |
13 |
Correct |
4 ms |
556 KB |
Output is correct |
14 |
Correct |
4 ms |
468 KB |
Output is correct |
15 |
Correct |
5 ms |
576 KB |
Output is correct |
16 |
Correct |
5 ms |
556 KB |
Output is correct |
17 |
Correct |
4 ms |
468 KB |
Output is correct |
18 |
Correct |
4 ms |
568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
2016 KB |
Output is correct |
2 |
Correct |
16 ms |
1492 KB |
Output is correct |
3 |
Correct |
30 ms |
2368 KB |
Output is correct |
4 |
Correct |
29 ms |
2296 KB |
Output is correct |
5 |
Correct |
30 ms |
2352 KB |
Output is correct |
6 |
Correct |
37 ms |
2896 KB |
Output is correct |
7 |
Correct |
25 ms |
1920 KB |
Output is correct |
8 |
Correct |
48 ms |
2912 KB |
Output is correct |
9 |
Correct |
42 ms |
2636 KB |
Output is correct |
10 |
Correct |
35 ms |
2696 KB |
Output is correct |
11 |
Correct |
34 ms |
2668 KB |
Output is correct |
12 |
Correct |
39 ms |
2760 KB |
Output is correct |
13 |
Correct |
36 ms |
2680 KB |
Output is correct |
14 |
Correct |
37 ms |
2784 KB |
Output is correct |
15 |
Correct |
44 ms |
2696 KB |
Output is correct |
16 |
Correct |
41 ms |
2788 KB |
Output is correct |
17 |
Correct |
41 ms |
2784 KB |
Output is correct |
18 |
Correct |
40 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
4280 KB |
Output is correct |
2 |
Correct |
48 ms |
3604 KB |
Output is correct |
3 |
Correct |
73 ms |
4856 KB |
Output is correct |
4 |
Correct |
11 ms |
952 KB |
Output is correct |
5 |
Correct |
81 ms |
5428 KB |
Output is correct |
6 |
Correct |
77 ms |
4300 KB |
Output is correct |
7 |
Correct |
87 ms |
4912 KB |
Output is correct |
8 |
Correct |
13 ms |
896 KB |
Output is correct |
9 |
Correct |
79 ms |
5328 KB |
Output is correct |
10 |
Correct |
70 ms |
5064 KB |
Output is correct |
11 |
Correct |
90 ms |
5008 KB |
Output is correct |
12 |
Correct |
76 ms |
5132 KB |
Output is correct |
13 |
Correct |
76 ms |
5436 KB |
Output is correct |
14 |
Correct |
73 ms |
5252 KB |
Output is correct |
15 |
Correct |
86 ms |
5164 KB |
Output is correct |
16 |
Correct |
96 ms |
5160 KB |
Output is correct |
17 |
Correct |
79 ms |
5152 KB |
Output is correct |
18 |
Correct |
68 ms |
5324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
105 ms |
7596 KB |
Output is correct |
2 |
Correct |
106 ms |
7544 KB |
Output is correct |
3 |
Correct |
83 ms |
6700 KB |
Output is correct |
4 |
Correct |
28 ms |
2832 KB |
Output is correct |
5 |
Correct |
116 ms |
8092 KB |
Output is correct |
6 |
Correct |
101 ms |
11104 KB |
Output is correct |
7 |
Correct |
75 ms |
6128 KB |
Output is correct |
8 |
Correct |
100 ms |
8016 KB |
Output is correct |
9 |
Correct |
133 ms |
9836 KB |
Output is correct |
10 |
Correct |
135 ms |
9836 KB |
Output is correct |
11 |
Correct |
128 ms |
9828 KB |
Output is correct |
12 |
Correct |
134 ms |
9804 KB |
Output is correct |
13 |
Correct |
173 ms |
9764 KB |
Output is correct |
14 |
Correct |
14 ms |
1292 KB |
Output is correct |
15 |
Correct |
175 ms |
10592 KB |
Output is correct |
16 |
Correct |
163 ms |
10424 KB |
Output is correct |
17 |
Correct |
161 ms |
10436 KB |
Output is correct |
18 |
Correct |
158 ms |
9852 KB |
Output is correct |