oj.uz

답안 #524623

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524623 2022-02-09T16:54:50 Z blue 학교 설립 (IZhO13_school) C++17
100 / 100
 184 ms 28896 KB 
#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

# 결과 실행 시간 메모리 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