oj.uz

Submission #58103

# Submission time Handle Problem Language Result Execution time Memory
58103 2018-07-16T20:29:43 Z Benq Schools (IZhO13_school) C++14
100 / 100
 177 ms 26060 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300005;

int N,M,S;
ll ansS[MX], ansM[MX];
vpi v;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> S;
    F0R(i,N) {
        int A,B; cin >> A >> B;
        v.pb({A,B});
    }
    sort(all(v),[](pi a, pi b){ return a.f-a.s < b.f-b.s; });
    priority_queue<int,vi,greater<int>> pq;
    ll sum = 0;
    F0R(i,N) {
        pq.push(v[i].s); sum += v[i].s;
        if (sz(pq) > S) { sum -= pq.top(); pq.pop(); }
        ansS[i+1] = sum;
    }
    while (sz(pq)) pq.pop();
    sum = 0;
    F0Rd(i,N) {
        pq.push(v[i].f); sum += v[i].f;
        if (sz(pq) > M) { sum -= pq.top(); pq.pop(); }
        ansM[i] = sum;
    }
    ll ans = 0;
    F0R(i,N+1) ans = max(ans,ansS[i]+ansM[i]);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 3 ms 544 KB Output is correct
5 Correct 3 ms 544 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 6 ms 896 KB Output is correct
8 Correct 5 ms 944 KB Output is correct
9 Correct 5 ms 1152 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 6 ms 1204 KB Output is correct
12 Correct 7 ms 1276 KB Output is correct
13 Correct 18 ms 2720 KB Output is correct
14 Correct 50 ms 4408 KB Output is correct
15 Correct 110 ms 7956 KB Output is correct
16 Correct 114 ms 11940 KB Output is correct
17 Correct 134 ms 14820 KB Output is correct
18 Correct 132 ms 18024 KB Output is correct
19 Correct 172 ms 21576 KB Output is correct
20 Correct 177 ms 26060 KB Output is correct