Submission #343819

# Submission time Handle Problem Language Result Execution time Memory
343819 2021-01-04T14:00:39 Z nandonathaniel Schools (IZhO13_school) C++14
100 / 100
119 ms 9308 KB
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=300005;

vector<pii> V;

long long pref[MAXN],suf[MAXN];
priority_queue<int> PQ;
priority_queue<int,vector<int>,greater<int> > PQ2;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int N,M,S,A,B;
	cin >> N >> M >> S;
	for(int i=1;i<=N;i++){
		cin >> A >> B;
		V.push_back({A,B});
	}
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	//gaboleh ada A yang ga dipilih buat music/sport tp > yang dipilih untuk music
	//gaboleh ada B yang ga dipilih buat music/sport tp > yang dipilih untuk sport
	suf[M+S]=0;
	for(int i=N-1;i>=M+S;i--)PQ.push(V[i].second);
	for(int i=M+S-1;i>=M;i--){
		PQ.push(V[i].second);
		suf[i]=suf[i+1]+PQ.top();
		PQ.pop();
	}
	long long ret=0;
	for(int i=0;i<=M-1;i++){
		pref[M-1]+=V[i].first;
		PQ2.push(V[i].first-V[i].second);
	}
	for(int i=M;i<=M+S-1;i++){
		PQ2.push(V[i].first-V[i].second);
		pref[i]=pref[i-1]+V[i].first-PQ2.top();
		PQ2.pop();
	}
	long long ans=0;
	for(int i=M-1;i<=M+S-1;i++){
		ans=max(ans,pref[i]+suf[i+1]);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message

school.cpp: In function 'int main()':
school.cpp:31:12: warning: unused variable 'ret' [-Wunused-variable]
   31 |  long long ret=0;
      |            ^~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 540 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 14 ms 1564 KB Output is correct
14 Correct 29 ms 2664 KB Output is correct
15 Correct 54 ms 5092 KB Output is correct
16 Correct 72 ms 6500 KB Output is correct
17 Correct 89 ms 7268 KB Output is correct
18 Correct 91 ms 7524 KB Output is correct
19 Correct 100 ms 8164 KB Output is correct
20 Correct 119 ms 9308 KB Output is correct