Submission #524623

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
524623	2022-02-09T16:54:50 Z	blue	Schools (IZhO13_school)	C++17	100 / 100	184 ms	28896 KB

school

#include <iostream>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

using ll = long long;
using vi = vector<int>;

const int mx = 300'000;

ll a[mx], b[mx];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M, S;
	cin >> N >> M >> S;

	for(int i = 0; i < N; i++) cin >> a[i] >> b[i];

	vi I(N);
	iota(I.begin(), I.end(), 0);
	sort(I.begin(), I.end(), [] (int x, int y)
	{
		return a[x] - b[x] > a[y] - b[y];
	});

	ll A[N], B[N];

	for(int i = 0; i < N; i++)
	{
		A[i] = a[I[i]];
		B[i] = b[I[i]];
	}





	ll Asum = 0;
	multiset<ll> Aset;
	ll Adp[N];

	for(int i = 0; i < M; i++) 
	{
		Aset.insert(A[i]);
		Asum += A[i];
	}

	Adp[M-1] = Asum;

	for(int i = M; i < N; i++)
	{
		Aset.insert(A[i]);	
		Asum += A[i];

		Asum -= *Aset.begin();
		Aset.erase(Aset.begin());

		Adp[i] = Asum;
	}





	ll Bsum = 0;
	multiset<ll> Bset;
	ll Bdp[N];

	for(int i = N-1; i >= N-S; i--)
	{
		Bset.insert(B[i]);
		Bsum += B[i];
	}

	Bdp[N-S] = Bsum;

	for(int i = N-S-1; i >= 0; i--)
	{
		Bset.insert(B[i]);
		Bsum += B[i];

		Bsum -= *Bset.begin();
		Bset.erase(Bset.begin());

		Bdp[i] = Bsum;
	}

	ll res = 0;

	for(int i = M-1; i < N-S; i++) res = max(res, Adp[i] + Bdp[i+1]);

	cout << res << '\n';
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	0 ms	320 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2 ms	584 KB	Output is correct
8	Correct	2 ms	760 KB	Output is correct
9	Correct	2 ms	704 KB	Output is correct
10	Correct	4 ms	716 KB	Output is correct
11	Correct	3 ms	708 KB	Output is correct
12	Correct	3 ms	708 KB	Output is correct
13	Correct	18 ms	4060 KB	Output is correct
14	Correct	35 ms	6468 KB	Output is correct
15	Correct	56 ms	10360 KB	Output is correct
16	Correct	112 ms	19732 KB	Output is correct
17	Correct	134 ms	22932 KB	Output is correct
18	Correct	139 ms	23364 KB	Output is correct
19	Correct	161 ms	25604 KB	Output is correct
20	Correct	184 ms	28896 KB	Output is correct