oj.uz

Submission #501424

# Submission time Handle Problem Language Result Execution time Memory
501424 2022-01-03T08:56:45 Z beksultan04 Schools (IZhO13_school) C++14
100 / 100
 214 ms 14980 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
#define pii pair<int,int>
#define ret return
#define fr first
#define sc second
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define nosol puts("-1");
#define pb push_back
#define endi puts("");
#define ordered_set tree <int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N = 5e5+12,INF = 1e9+7;

int pref[N],suff[N];

bool comp(pii a,pii b){
	
	ret (a.fr-a.sc)>(b.fr-b.sc);
	
}

main(){
	int n,i,a,b,ans=0,sum=0;
	cin>>n>>a>>b;
	vector <pii> v;
	for (i=1;i<=n;++i){
		int x,y;
		cin>>x>>y;
		v.pb({x,y});
	}
	sort(all(v),comp);
	priority_queue <int,vector <int> ,greater<int> > q;
	for (i=0;i<n;++i){
		sum += v[i].fr;
		q.push(v[i].fr);
		if (q.size() > a){
			sum -= q.top();
			q.pop();
		}
		pref[i] = sum;
	}
	sum = 0;
	while (!q.empty())q.pop();
	for (i=n-1;i>=0;--i){
		sum += v[i].sc;
		q.push(v[i].sc);
		if (q.size() > b){
			sum -= q.top();
			q.pop();
		}
		suff[i] = sum;
	}
	for (i=0;i<n;++i){
		ans = max(ans,pref[i]+suff[i+1]);
	}
	cout <<ans;
	
	
}

Compilation message

school.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main(){
      | ^~~~
school.cpp: In function 'int main()':
school.cpp:44:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |   if (q.size() > a){
      |       ~~~~~~~~~^~~
school.cpp:55:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   55 |   if (q.size() > b){
      |       ~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 4 ms 588 KB Output is correct
10 Correct 5 ms 588 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 28 ms 2208 KB Output is correct
14 Correct 55 ms 3960 KB Output is correct
15 Correct 109 ms 7228 KB Output is correct
16 Correct 126 ms 11128 KB Output is correct
17 Correct 162 ms 11488 KB Output is correct
18 Correct 183 ms 12500 KB Output is correct
19 Correct 191 ms 13256 KB Output is correct
20 Correct 214 ms 14980 KB Output is correct