Submission #313290

#	Time	Username	Problem	Language	Result	Execution time	Memory
313290		vitkishloh228	Schools (IZhO13_school)	C++14	95 / 100	415 ms	17160 KiB

school

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
int32_t main() {
	int n, m, s;
	cin >> n >> m >> s;
	vector<int> M(n), S(n);
	vector<pair<int, int>> ar;
	for (int i = 0; i < n; ++i) {
		cin >> M[i] >> S[i];
		ar.push_back({ M[i] - S[i],i });
	}
	sort(ar.rbegin(), ar.rend());
	//reverse(ar.begin(), ar.end());
	vector<int> pr(n), suf(n + 1);
	priority_queue< long long, vector<long long>, greater<long long> >q;
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		int pos = ar[i].second;
		if (q.size() < m) {
			sum += M[pos];
			q.push(M[pos]);
			pr[i] = sum;
			continue;
		}
		if (q.top() < M[pos]) {
			sum -= q.top();
			q.pop();
			sum += M[pos];
			q.push(M[pos]);
		}
		pr[i] = sum;
	}
	sum = 0;
	priority_queue< long long, vector<long long>, greater<long long> >q1;
	for (int i = n - 1; i >= 0; --i) {
		int pos = ar[i].second;
		if (q1.size() < s) {
			sum += S[pos];
			q1.push(S[pos]);
			suf[i] = sum;
			continue;
		}
		if (q1.top() < S[pos]) {
			sum -= q1.top();
			q1.pop();
			sum += S[pos];
			q1.push(S[pos]);
		}
		suf[i] = sum;
	}
	int ans = suf[0];
	for (int i = 0; i < n; ++i) {
		ans = max(ans, pr[i] + suf[i + 1]);
	}
	cout << ans;
}

Compilation message (stderr)

school.cpp: In function 'int32_t main()':
school.cpp:23: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]
   23 |   if (q.size() < m) {
      |       ~~~~~~~~~^~~
school.cpp:41:17: 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]
   41 |   if (q1.size() < s) {
      |       ~~~~~~~~~~^~~

• Subtask 1: 95 / 100