Submission #84459

#	Time	Username	Problem	Language	Result	Execution time	Memory
84459		talip	Schools (IZhO13_school)	C++14	100 / 100	179 ms	9364 KiB

school

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, m, q, a[N], b[N], p[N];
long long int f[N], g[N], s, res;
 //Memory leak with vector......
 //Will test against greater<int>
bool fark(int x, int y) {
    return a[x] - b[x] < a[y] - b[y];
}
 
int main() {
    ios::sync_with_stdio(false);	cin.tie(NULL);	cout.tie(NULL);
    cin >> n >> m >> q;
    for (int i = 0; i < n; ++i){
    	cin >> a[i] >> b[i];
    }
    for (int i = 0; i < n; ++i){
    	p[i] = i;
    }
    sort(p, p + n, fark);    priority_queue<int> pq;	s = 0;
    for(int i = 0; i < n; ++i) {
        pq.push(-b[p[i]]); s += b[p[i]];
        if (pq.size()>q) {
            s += pq.top(); pq.pop();
        }
        f[i] = s;
    }
    while(pq.size()){
    	pq.pop();
    }
    s = 0;
    for(int i=n-1;i>=0;i--){
        pq.push(-a[p[i]]); s += a[p[i]];
        if (pq.size()>m) {
            s+=pq.top();	pq.pop();
        }
        g[i] = s;
    }
    for (int i = q - 1; i < n - m; ++i){
    	res = max(res, f[i] + g[i + 1]);
    }
    cout << res;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size()>q) {
             ~~~~~~~~~^~
school.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pq.size()>m) {
             ~~~~~~~~~^~

• Subtask 1: 100 / 100