# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
401363 | wnsduds1 | 학교 설립 (IZhO13_school) | C11 | 176 ms | 11968 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |