oj.uz

Submission #251999

# Submission time Handle Problem Language Result Execution time Memory
251999 2020-07-23T14:31:29 Z aZvezda Schools (IZhO13_school) C++14
100 / 100
 158 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;
    if(m == 0) {pref[0] = 0;}
    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;
    if(s == 0) {suf[n] = 0;}
    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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 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 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 2 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 34 ms 3828 KB Output is correct
15 Correct 65 ms 6648 KB Output is correct
16 Correct 74 ms 9324 KB Output is correct
17 Correct 106 ms 10604 KB Output is correct
18 Correct 120 ms 11248 KB Output is correct
19 Correct 126 ms 12144 KB Output is correct
20 Correct 158 ms 13808 KB Output is correct