oj.uz

Submission #251995

# Submission time Handle Problem Language Result Execution time Memory
251995 2020-07-23T14:21:23 Z aZvezda Schools (IZhO13_school) C++14
95 / 100
 141 ms 17392 KB 
#include <bits/stdc++.h>
using namespace std;
//T+N
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl

const ll MAX_N = 3e5 + 10;
bool used[MAX_N];
pair<ll, pair<ll, ll> > toSrt[MAX_N];

struct HeapSum {
    ll sum = 0, limit = -1;
    priority_queue<ll> pq;
    HeapSum() {}
    HeapSum(ll _limit) : limit(_limit) {}
    void push(ll x) {
        pq.push(-x);
        sum += x;
        if(pq.size() > limit) {
            sum += pq.top();
            pq.pop();
        }
    }
    ll ans() {
        if(pq.size() != limit) {
            return -mod * mod;
        } else {
            return sum;
        }
    }
};

ll pref[MAX_N], suf[MAX_N];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n, m, s;
    cin >> n >> m >> s;
    for(ll i = 0; i < n; i ++) {
        ll a, b;
        cin >> a >> b;
        toSrt[i] = {b - a, {a, b}};
    }
    sort(toSrt, toSrt + n);
    HeapSum music(m), sport(s);
    pref[0] = -mod * mod;
    for(ll i = 0; i < n; i ++) {
        music.push(toSrt[i].second.first);
        pref[i + 1] = music.ans();
    }
    ll ret = -mod * mod;
    suf[n] = -mod * mod;
    for(ll i = n - 1; i >= 0; i --) {
        sport.push(toSrt[i].second.second);
        suf[i] = sport.ans();
    }
    for(ll i = 0; i <= n; i ++) {
        chkmax(ret, pref[i] +  suf[i]);
    }
    cout << ret << endl;
    return 0;
}

Compilation message

school.cpp: In member function 'void HeapSum::push(ll)':
school.cpp:28:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pq.size() > limit) {
            ~~~~~~~~~~^~~~~~~
school.cpp: In member function 'll HeapSum::ans()':
school.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pq.size() != limit) {
            ~~~~~~~~~~^~~~~~~~

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 256 KB Output isn't correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 14 ms 2552 KB Output is correct
14 Correct 33 ms 4596 KB Output is correct
15 Correct 64 ms 8440 KB Output is correct
16 Correct 73 ms 11372 KB Output is correct
17 Correct 101 ms 13040 KB Output is correct
18 Correct 120 ms 14064 KB Output is correct
19 Correct 123 ms 15212 KB Output is correct
20 Correct 141 ms 17392 KB Output is correct