typedef struct list {
int num;
int l, r;
}list;
void insert(list *x, list value, int ver);
list del(list *x, int ver);
void compare(list *x, list *y, list value, int ver);
int bottom_x = 0;
int bottom_y = 0;
int m, s;
int c[300001] = { 0, };
int main()
{
list arr[300001];
list x[300001];
list y[300001];
list tmp;
list value1,value2,value;
int n;
int i, j, k;
long long sum = 0;
scanf("%d %d %d", &n, &m, &s);
for (i = 0; i < n; i++)
{
scanf("%d %d", &value.l, &value.r);
value.num = i;
arr[i] = value;
insert(x, value, 1);
insert(y, value, 2);
}
while (m != 0 || s != 0)
{
if (m > 0)
{
value1 = del(x, 1);
if (c[value1.num] != 0)
{
compare(x, y, value1,1);
}
else {
c[value1.num] = 1;
m -= 1;
}
}
if (s > 0)
{
value2 = del(y, 2);
if (c[value2.num] != 0)
{
compare(x, y, value1,2);
}
else {
c[value2.num] = 2;
s -= 1;
}
}
}
for (i = 0; i < n; i++)
{
if (c[i] != 0)
{
if (c[i] == 1)
{
sum += (long long)arr[i].l;
}
else {
sum += (long long)arr[i].r;
}
}
}
printf("%lld", sum);
return 0;
}
void compare(list *x, list *y, list value,int ver)
{
list value1, value2;
value1 = del(x, 1);
value2 = del(y, 2);
if (ver == 1)
{
if (value.l + value1.r > value.r + value2.l)
{
c[value.num] = 2;
c[value1.num] = 1;
m -= 1;
insert(y, value2, 2);
}
else {
c[value.num] = 1;
c[value2.num] = 2;
m -= 1;
insert(x, value1, 1);
}
}
else {
if (value.l + value2.r > value.r + value1.l)
{
c[value.num] = 1;
c[value2.num] = 2;
s -= 1;
insert(x, value1, 1);
}
else {
c[value.num] = 2;
c[value1.num] = 1;
s -= 1;
insert(y, value2, 2);
}
}
}
void insert(list *x, list value, int ver)
{
if (ver == 1)
{
if (bottom_x == 0)
{
bottom_x += 1;
x[bottom_x] = value;
}
else {
int index;
list tmp;
bottom_x += 1;
x[bottom_x] = value;
index = bottom_x;
while (index != 1 && x[index].l > x[index / 2].l)
{
tmp = x[index];
x[index] = x[index / 2];
x[index / 2] = tmp;
index /= 2;
}
}
}
else {
if (bottom_y == 0)
{
bottom_y += 1;
x[bottom_y] = value;
}
else {
int index;
list tmp;
bottom_y += 1;
x[bottom_y] = value;
index = bottom_y;
while (index != 1 && x[index].r > x[index / 2].r)
{
tmp = x[index];
x[index] = x[index / 2];
x[index / 2] = tmp;
index /= 2;
}
}
}
}
list del(list *x, int ver)
{
list tmp;
list return_value;
int index = 1;
if (ver == 1)
{
return_value = x[index];
x[index] = x[bottom_x];
bottom_x -= 1;
while ((index * 2 <= bottom_x) && (x[index].l < x[index * 2].l || x[index].l < x[index * 2 + 1].l))
{
if (x[index * 2].l < x[index * 2 + 1].l)
{
tmp = x[index];
x[index] = x[index * 2 + 1];
x[index * 2 + 1] = tmp;
index = index * 2 + 1;
}
else {
tmp = x[index];
x[index] = x[index * 2];
x[index * 2] = tmp;
index = index * 2;
}
}
}
else {
return_value = x[index];
x[index] = x[bottom_y];
bottom_y -= 1;
while ((index * 2 <= bottom_y) && (x[index].r < x[index * 2].r ||x[index].r < x[index * 2 + 1].r))
{
if (x[index * 2].r < x[index * 2 + 1].r)
{
tmp = x[index];
x[index] = x[index * 2 + 1];
x[index * 2 + 1] = tmp;
index = index * 2 + 1;
}
else {
tmp = x[index];
x[index] = x[index * 2];
x[index * 2] = tmp;
index = index * 2;
}
}
}
return return_value;
}
Compilation message
school.c: In function 'main':
school.c:22:2: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
22 | scanf("%d %d %d", &n, &m, &s);
| ^~~~~
school.c:22:2: warning: incompatible implicit declaration of built-in function 'scanf'
school.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
+++ |+#include <stdio.h>
1 | typedef struct list {
school.c:74:2: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
74 | printf("%lld", sum);
| ^~~~~~
school.c:74:2: warning: incompatible implicit declaration of built-in function 'printf'
school.c:74:2: note: include '<stdio.h>' or provide a declaration of 'printf'
school.c:20:12: warning: unused variable 'k' [-Wunused-variable]
20 | int i, j, k;
| ^
school.c:20:9: warning: unused variable 'j' [-Wunused-variable]
20 | int i, j, k;
| ^
school.c:17:7: warning: unused variable 'tmp' [-Wunused-variable]
17 | list tmp;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
432 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
548 KB |
Output isn't correct |
| 11 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 12 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 13 |
Incorrect |
16 ms |
2124 KB |
Output isn't correct |
| 14 |
Incorrect |
29 ms |
4180 KB |
Output isn't correct |
| 15 |
Incorrect |
47 ms |
8132 KB |
Output isn't correct |
| 16 |
Incorrect |
88 ms |
9188 KB |
Output isn't correct |
| 17 |
Incorrect |
114 ms |
11344 KB |
Output isn't correct |
| 18 |
Incorrect |
125 ms |
12512 KB |
Output isn't correct |
| 19 |
Incorrect |
134 ms |
13472 KB |
Output isn't correct |
| 20 |
Incorrect |
146 ms |
15404 KB |
Output isn't correct |
