oj.uz

답안 #89109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
89109 2018-12-10T10:14:40 Z nika 학교 설립 (IZhO13_school) C++14
100 / 100
 149 ms 8468 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 380 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 548 KB Output is correct
4 Correct 2 ms 548 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 4 ms 664 KB Output is correct
8 Correct 4 ms 788 KB Output is correct
9 Correct 5 ms 832 KB Output is correct
10 Correct 4 ms 832 KB Output is correct
11 Correct 4 ms 832 KB Output is correct
12 Correct 4 ms 832 KB Output is correct
13 Correct 18 ms 1604 KB Output is correct
14 Correct 39 ms 2528 KB Output is correct
15 Correct 71 ms 4256 KB Output is correct
16 Correct 87 ms 4920 KB Output is correct
17 Correct 106 ms 6452 KB Output is correct
18 Correct 117 ms 7040 KB Output is correct
19 Correct 127 ms 7692 KB Output is correct
20 Correct 149 ms 8468 KB Output is correct