oj.uz

Submission #504053

# Submission time Handle Problem Language Result Execution time Memory
504053 2022-01-09T15:15:20 Z PoPularPlusPlus Schools (IZhO13_school) C++17
100 / 100
 98 ms 17396 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

void solve(){
	int n;
	cin >> n;
	int m , k;
	cin >> m >> k;;
	ll a[n] , b[n];
	vector<pair<int,int>> v;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		v.pb(mp(a[i] - b[i] , i));
	}
	sv(v);
	reverse(all(v));
	ll pre[n] , suf[n];
	memset(pre , 0 , sizeof pre);
	memset(suf , 0 , sizeof suf);
	ll sum = 0;
	if(m > 0){
	priority_queue<ll , vector<ll> , greater<ll> > q;
	for(int i = 0; i < m; i++){
		sum += a[v[i].vs];
		q.push(a[v[i].vs]);
	}
	pre[m - 1] = sum;
	for(int i = m; i < n; i++){
		if(q.top() < a[v[i].vs]){
			sum -= q.top();
			q.pop();
			q.push(a[v[i].vs]);
			sum += a[v[i].vs];
		}
		pre[i] = sum;
	}
	}
	sum = 0;
	if(k > 0){
	priority_queue<ll , vector<ll> , greater<ll> > pq;
	for(int i = n - 1; i >= n - k; i--){
		pq.push(b[v[i].vs]);
		sum += b[v[i].vs];
	}
	suf[n - k] = sum;
	for(int i = n - (k + 1); i >= 0; i--){
		if(pq.top() < b[v[i].vs]){
			sum -= pq.top();
			sum += b[v[i].vs];
			pq.pop();
			pq.push(b[v[i].vs]);
		}
		suf[i] = sum;
	}
	}
	ll ans = 0;
	if(m == 0){
		ans = suf[0];
	}
	else if(k == 0){
		ans = pre[n - 1];
	}
	else {
		for(int i = m - 1; i < n - k; i++){
			ans = max(ans , pre[i] + suf[i + 1]);
		}
	}
	cout << ans << '\n';
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("school.in", "r", stdin);
//freopen("school.out", "w", stdout);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 584 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 15 ms 2596 KB Output is correct
14 Correct 33 ms 4548 KB Output is correct
15 Correct 57 ms 8372 KB Output is correct
16 Correct 57 ms 12392 KB Output is correct
17 Correct 75 ms 13240 KB Output is correct
18 Correct 78 ms 14268 KB Output is correct
19 Correct 90 ms 15204 KB Output is correct
20 Correct 98 ms 17396 KB Output is correct