Submission #89109

#	Time	Username	Problem	Language	Result	Execution time	Memory
89109		nika	Schools (IZhO13_school)	C++14	100 / 100	149 ms	8468 KiB

school

#include<bits/stdc++.h>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int n, m, s;
struct st {
    int a, b;
    void scan() {
        scanf("%d%d", &a, &b);
    }
    bool operator<(const st &p) const {
        return a - b < p.a - p.b;
    }
} ss[300000];
 
struct pq {
    priority_queue<int, vector<int>, greater<int>> q; int sz; llong sum;
    pq(int sz) : sz(sz), sum(0) {}
    void push(int x) {
        q.push(x);
        sum += x;
        if (sz < q.size()) {
            sum -= q.top();
            q.pop();
        }
    }
};
 
llong as[300000];
llong bs[300000];
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < n; ++i) ss[i].scan();
    sort(ss, ss + n);
    {
        pq q(s);
        for (int i = 0; i < n; ++i) {
            q.push(ss[i].b);
            bs[i] = q.sum;
        }
    }
    {
        pq q(m);
        for (int i = n; i--; ) {
            q.push(ss[i].a);
            as[i] = q.sum;
        }
    }
    llong ans = max(bs[n - 1], as[0]);
    for (int i = 1; i < n; ++i) {
        ans = max(ans, bs[i - 1] + as[i]);
    }
    printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In member function 'void pq::push(int)':
school.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (sz < q.size()) {
             ~~~^~~~~~~~~~
school.cpp: In function 'int main()':
school.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp: In member function 'void st::scan()':
school.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100