Submission #249731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
249731	2020-07-15T16:13:11 Z	srvlt	Schools (IZhO13_school)	C++14	100 / 100	205 ms	15224 KB

school

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int n0 = 3e5 + 123;
int n, m, s;
ll suf[n0];

struct Pair {
	int x, y;
	bool operator < (const Pair & p) const {
		return x - y > p.x - p.y;
	}
};
Pair p[n0];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> m >> s;
	for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
	sort(p, p + n);
	multiset <int> A, B;
	for (int i = n - 1; i >= 0; i--) {
		suf[i] = suf[i + 1] + p[i].y;
		B.insert(p[i].y);
		if (SZ(B) > s) {
			suf[i] -= *B.begin();
			B.erase(B.begin());
		}
	}
	ll cur = 0, res = 0;
	for (int i = 0; i < n - s; i++) {
		cur += p[i].x;
		A.insert(p[i].x);
		if (SZ(A) > m) {
			cur -= *A.begin();
			A.erase(A.begin());
		}
		if (i >= m - 1) res = max(res, cur + suf[i + 1]);
	}
	cout << res;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	3 ms	640 KB	Output is correct
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	3 ms	640 KB	Output is correct
12	Correct	3 ms	640 KB	Output is correct
13	Correct	23 ms	2808 KB	Output is correct
14	Correct	46 ms	3320 KB	Output is correct
15	Correct	65 ms	3448 KB	Output is correct
16	Correct	147 ms	11896 KB	Output is correct
17	Correct	171 ms	12968 KB	Output is correct
18	Correct	164 ms	12540 KB	Output is correct
19	Correct	180 ms	13816 KB	Output is correct
20	Correct	205 ms	15224 KB	Output is correct