oj.uz

Submission #251997

# Submission time Handle Problem Language Result Execution time Memory
251997 2020-07-23T14:24:41 Z aZvezda Schools (IZhO13_school) C++14
95 / 100
 142 ms 13808 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 = 1e7 + 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 = 0;
    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 0 ms 384 KB Output is correct
2 Incorrect 0 ms 384 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 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 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 2176 KB Output is correct
14 Correct 32 ms 3832 KB Output is correct
15 Correct 59 ms 6648 KB Output is correct
16 Correct 75 ms 9324 KB Output is correct
17 Correct 101 ms 10480 KB Output is correct
18 Correct 110 ms 11248 KB Output is correct
19 Correct 119 ms 12140 KB Output is correct
20 Correct 142 ms 13808 KB Output is correct