oj.uz

Submission #21854

# Submission time Handle Problem Language Result Execution time Memory
21854 2017-04-26T12:37:30 Z ulna Schools (IZhO13_school) C++11
0 / 100
 0 ms 5540 KB 
#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;
			c.pop();
			a.pop();
		}
	}

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

	return 0;
}

Compilation message

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5540 KB Output is correct
2 Correct 0 ms 5540 KB Output is correct
3 Correct 0 ms 5540 KB Output is correct
4 Incorrect 0 ms 5540 KB Output isn't correct
5 Halted 0 ms 0 KB -