Submission #446098

#	Time	Username	Problem	Language	Result	Execution time	Memory
446098		aryan12	Schools (IZhO13_school)	C++17	75 / 100	142 ms	10688 KiB

school

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first - a.second > b.first - b.second;
}

void Solve() {
	int n, m, s;
	cin >> n >> m >> s;
	vector<pair<int, int> > a(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin() + 1, a.end(), cmp);
	priority_queue<int, vector<int>, greater<int> > pq;
	int pref[n + 1];
	pref[0] = 0;
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		pq.push(a[i].first);
		sum += a[i].first;
		//cout << "sum = " << sum << "\n";
		while(pq.size() > m) {
			int x = pq.top();
			pq.pop();
			sum -= x;
		}
		//cout << "sum = " << sum << "\n";
		pref[i] = sum;
	}
	while(!pq.empty()) {
		pq.pop();
	}
	int suf[n + 2];
	suf[n + 1] = 0;
	sum = 0;
	for(int i = n; i > 0; i--) {
		pq.push(a[i].second);
		sum += a[i].second;
		while(pq.size() > s) {
			int x = pq.top();
			pq.pop();
			sum -= x;
		}
		suf[i] = sum;
	}
	/*for(int i = 1; i <= n; i++) {
		cout << pref[i] << " ";
	}
	cout << "\n";
	for(int i = n; i > 0; i--) {
		cout << suf[i] << " ";
	}
	cout << "\n";*/
	int ans = 0;
	for(int i = m; i < n - s; i++) {
		ans = max(ans, pref[i] + suf[i + 1]);
	}
	cout << ans << "\n";
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'void Solve()':
school.cpp:27:19: 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]
   27 |   while(pq.size() > m) {
      |         ~~~~~~~~~~^~~
school.cpp:44:19: 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 |   while(pq.size() > s) {
      |         ~~~~~~~~~~^~~

• Subtask 1: 75 / 100