oj.uz

Submission #73820

# Submission time Handle Problem Language Result Execution time Memory
73820 2018-08-29T05:17:29 Z 강태규(#2274) Schools (IZhO13_school) C++11
95 / 100
 158 ms 8636 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 = 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
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 504 KB Output isn't correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 648 KB Output is correct
7 Correct 5 ms 764 KB Output is correct
8 Correct 4 ms 764 KB Output is correct
9 Correct 6 ms 764 KB Output is correct
10 Correct 4 ms 764 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 19 ms 1644 KB Output is correct
14 Correct 44 ms 2568 KB Output is correct
15 Correct 81 ms 4332 KB Output is correct
16 Correct 101 ms 4964 KB Output is correct
17 Correct 125 ms 6504 KB Output is correct
18 Correct 132 ms 7072 KB Output is correct
19 Correct 157 ms 7496 KB Output is correct
20 Correct 158 ms 8636 KB Output is correct