oj.uz

Submission #251996

# Submission time Handle Problem Language Result Execution time Memory
251996 2020-07-23T14:24:04 Z aZvezda Schools (IZhO13_school) C++14
95 / 100
 140 ms 13932 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 = -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 384 KB Output isn't correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 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 2 ms 632 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 15 ms 2296 KB Output is correct
14 Correct 34 ms 3956 KB Output is correct
15 Correct 63 ms 6780 KB Output is correct
16 Correct 80 ms 9452 KB Output is correct
17 Correct 112 ms 10608 KB Output is correct
18 Correct 115 ms 11400 KB Output is correct
19 Correct 121 ms 12268 KB Output is correct
20 Correct 140 ms 13932 KB Output is correct