#include<stdio.h>
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:21:12: warning: unused variable 'k' [-Wunused-variable]
21 | int i, j, k;
| ^
school.c:21:9: warning: unused variable 'j' [-Wunused-variable]
21 | int i, j, k;
| ^
school.c:18:7: warning: unused variable 'tmp' [-Wunused-variable]
18 | list tmp;
| ^~~
school.c:23:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
23 | scanf("%d %d %d", &n, &m, &s);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.c:26:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
26 | scanf("%d %d", &value.l, &value.r);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
204 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
460 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
460 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 |
1716 KB |
Output isn't correct |
| 14 |
Incorrect |
29 ms |
3332 KB |
Output isn't correct |
| 15 |
Incorrect |
48 ms |
6468 KB |
Output isn't correct |
| 16 |
Incorrect |
88 ms |
7304 KB |
Output isn't correct |
| 17 |
Incorrect |
119 ms |
8804 KB |
Output isn't correct |
| 18 |
Incorrect |
120 ms |
9760 KB |
Output isn't correct |
| 19 |
Incorrect |
135 ms |
10600 KB |
Output isn't correct |
| 20 |
Incorrect |
176 ms |
11968 KB |
Output isn't correct |
