oj.uz

답안 #89100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89100 2018-12-10T10:04:36 Z anri 학교 설립 (IZhO13_school) C++14
100 / 100
 146 ms 8692 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 4 ms 540 KB Output is correct
8 Correct 4 ms 620 KB Output is correct
9 Correct 4 ms 676 KB Output is correct
10 Correct 4 ms 720 KB Output is correct
11 Correct 4 ms 720 KB Output is correct
12 Correct 4 ms 748 KB Output is correct
13 Correct 17 ms 1644 KB Output is correct
14 Correct 38 ms 2484 KB Output is correct
15 Correct 75 ms 4460 KB Output is correct
16 Correct 86 ms 4964 KB Output is correct
17 Correct 108 ms 6584 KB Output is correct
18 Correct 115 ms 7160 KB Output is correct
19 Correct 128 ms 7496 KB Output is correct
20 Correct 146 ms 8692 KB Output is correct