oj.uz

Submission #390866

# Submission time Handle Problem Language Result Execution time Memory
390866 2021-04-17T09:11:02 Z SavicS Schools (IZhO13_school) C++14
100 / 100
 346 ms 26180 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 300005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, M, S;
pii niz[maxn];

int main() 
{
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cin >> n >> M >> S;
    ff(i,1,n)cin >> niz[i].fi >> niz[i].se;

    sort(niz + 1, niz + n + 1);
    reverse(niz + 1, niz + n + 1);

    multiset<int> C;
    multiset<pii> A, B;

    ll rez = 0;
    ff(i,1,M) {
        rez += niz[i].fi;
        C.insert(niz[i].se - niz[i].fi);
    }

    ff(i,M + 1, n) {
        A.insert({niz[i].fi, i});
        B.insert({niz[i].se, i});
    }

    ff(i,1,S) {

        pii X = *B.rbegin();
        pii Y = {*C.rbegin() + A.rbegin()->fi, A.rbegin()->se};

        if(X.fi >= Y.fi) {
            rez += X.fi;

            B.erase(B.find(X));
            A.erase(A.find({niz[X.se].fi, X.se}));

        } else {
            rez += Y.fi;

            C.erase(C.find(*C.rbegin()));
            B.erase(B.find({niz[Y.se].se, Y.se}));
            A.erase(A.find(*A.rbegin()));
            C.insert(niz[Y.se].se - niz[Y.se].fi);
        }

    }

    cout << rez << endl;

    return 0;
}
/**

7 2 3
9 8
10 6
3 5
1 7
5 7
6 3
5 4

3 1 1
5 2
4 1
6 4

// probati bojenje sahovski ili slicno

**/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 4 ms 716 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 4 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 21 ms 2444 KB Output is correct
14 Correct 91 ms 8016 KB Output is correct
15 Correct 189 ms 16352 KB Output is correct
16 Correct 333 ms 17564 KB Output is correct
17 Correct 259 ms 18632 KB Output is correct
18 Correct 252 ms 20292 KB Output is correct
19 Correct 300 ms 22372 KB Output is correct
20 Correct 346 ms 26180 KB Output is correct