Submission #1029100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029100		Nurislam	Schools (IZhO13_school)	C++17	95 / 100	115 ms	16596 KiB

school

#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 pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>  
#define int long long

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
const int N = 2e5+5, inf = 1e18, mod = 1e9+7;

void solve() {
	int n, m, s;
	cin >> n >> m >> s;
	vector<int> a(n), b(n), idx(n);
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	for(int i = 0; i < n; i++)idx[i] = i;
	auto cp = [&](int &x,int &y) -> bool{
		return (a[x] - b[x]) > (a[y] - b[y]);
	};
	sort(all(idx), cp);
	//for(auto i:idx)cout << i << '\n';
	priority_queue<int> q;
	int pre[n]{}, suf[n+1]{};
	for(int i = 0; i < n; i++){
		pre[i] = (i?pre[i-1]:0);
		q.push(-a[idx[i]]);
		pre[i] += a[idx[i]];
		while(q.size() > m){
			pre[i]+=q.top();q.pop();
		}
	}
	while(q.size())q.pop();
	for(int i = n-1; i>=0; i--){
		suf[i] = suf[i+1];
		q.push(-b[idx[i]]);
		suf[i] += b[idx[i]];
		while(q.size() > s){
			suf[i]+=q.top();q.pop();
		}
	}
	//for(auto i:pre)cout << i << ' ';
	//cout << '\n';
	//for(auto i:suf)cout << i << ' ';
	//cout << '\n';
	int ans = 0;
	for(int i = 0; i < n-1; i++)chmax(ans, pre[i]+suf[i+1]);
	cout << ans << '\n';
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

Compilation message (stderr)

school.cpp: In function 'void solve()':
school.cpp:53:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   53 |   while(q.size() > m){
      |         ~~~~~~~~~^~~
school.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   62 |   while(q.size() > s){
      |         ~~~~~~~~~^~~

• Subtask 1: 95 / 100