oj.uz

Submission #73821

# Submission time Handle Problem Language Result Execution time Memory
73821 2018-08-29T05:19:17 Z 강태규(#2274) Schools (IZhO13_school) C++11
100 / 100
 152 ms 8584 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

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

school.cpp: In member function 'void pq::push(int)':
school.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (sz < q.size()) {
             ~~~^~~~~~~~~~
school.cpp: In function 'int main()':
school.cpp:48: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:25: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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 4 ms 672 KB Output is correct
8 Correct 5 ms 672 KB Output is correct
9 Correct 4 ms 692 KB Output is correct
10 Correct 5 ms 696 KB Output is correct
11 Correct 4 ms 788 KB Output is correct
12 Correct 4 ms 788 KB Output is correct
13 Correct 21 ms 1636 KB Output is correct
14 Correct 51 ms 2564 KB Output is correct
15 Correct 81 ms 4396 KB Output is correct
16 Correct 90 ms 4956 KB Output is correct
17 Correct 119 ms 6572 KB Output is correct
18 Correct 128 ms 7080 KB Output is correct
19 Correct 129 ms 7544 KB Output is correct
20 Correct 152 ms 8584 KB Output is correct