Submission #401364

#	Time	Username	Problem	Language	Result	Execution time	Memory
401364		wnsduds1	Schools (IZhO13_school)	C11	5 / 100	195 ms	11964 KiB

school

#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, value2,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 (stderr)

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);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 100