Submission #21855

#	Time	Username	Problem	Language	Result	Execution time	Memory
21855		ulna	Schools (IZhO13_school)	C++11	100 / 100	176 ms	10208 KiB

school

#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n, m, s;
int a[300055], b[300055];

int group[300055];

struct compare1 {
	bool operator () (const int &u, const int &v) const {
		return a[u] < a[v];
	}
} ;
struct compare2 { 
	bool operator () (const int &u, const int &v) const {
		return b[u] < b[v];
	}
} ;
int main() {
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &a[i], &b[i]);
	}

	vector<int> vec(n);

	for (int i = 0; i < n; i++) vec[i] = i;

	sort(vec.begin(), vec.end(), [&] (int u, int v) {
		return a[u] > a[v];
	});

	long long res = 0ll;

	// from a->b, nothing->a, -a[i] + b[i] + a[j]
	// from nothing->b, +b[j]
		
	priority_queue<int> a;
	priority_queue<int, vector<int>, compare1> c;
	priority_queue<int, vector<int>, compare2> d;

	for (int i = 0; i < m; i++) {
		res += ::a[vec[i]];
		group[vec[i]] = 1;
		a.push(-::a[vec[i]] + b[vec[i]]);
	}

	for (int i = m; i < n; i++) {
		c.push(vec[i]);
		d.push(vec[i]);
	}

	for (int i = 0; i < s; i++) {
		while (group[c.top()] != 0) c.pop();
		while (group[d.top()] != 0) d.pop();

		if (a.empty() || a.top() + ::a[c.top()] < b[d.top()]) {
			res += b[d.top()];
			group[d.top()] = 2;
			d.pop();
		} else {
			res += a.top() + ::a[c.top()];
			group[c.top()] = 1;
			a.pop();
			a.push(-::a[c.top()] + b[c.top()]);
			c.pop();
		}
	}

	printf("%lld\n", res);

	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:22:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &s);
                               ^
school.cpp:25:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
                               ^

• Subtask 1: 100 / 100