Submission #524623

#	Time	Username	Problem	Language	Result	Execution time	Memory
524623		blue	Schools (IZhO13_school)	C++17	100 / 100	184 ms	28896 KiB

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 / 100