oj.uz

Submission #625486

# Submission time Handle Problem Language Result Execution time Memory
625486 2022-08-10T13:31:19 Z PoPularPlusPlus Schools (IZhO13_school) C++17
100 / 100
 112 ms 19756 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<ll,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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 324 KB Output is correct
6 Correct 0 ms 324 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 12 ms 2896 KB Output is correct
14 Correct 27 ms 5232 KB Output is correct
15 Correct 47 ms 9532 KB Output is correct
16 Correct 67 ms 13940 KB Output is correct
17 Correct 73 ms 14932 KB Output is correct
18 Correct 79 ms 16184 KB Output is correct
19 Correct 101 ms 17336 KB Output is correct
20 Correct 112 ms 19756 KB Output is correct