답안 #401362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401362 2021-05-10T02:38:51 Z wnsduds1 학교 설립 (IZhO13_school) C
5 / 100
146 ms 15404 KB
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;
      |       ^~~
# 결과 실행 시간 메모리 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