oj.uz

Submission #390865

# Submission time Handle Problem Language Result Execution time Memory
390865 2021-04-17T09:10:19 Z SavicS Schools (IZhO13_school) C++14
0 / 100
 350 ms 29924 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});
    }

    cout << "rez: " << rez << endl;

    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 5 ms 852 KB Output isn't correct
8 Incorrect 3 ms 580 KB Output isn't correct
9 Incorrect 3 ms 588 KB Output isn't correct
10 Incorrect 3 ms 588 KB Output isn't correct
11 Incorrect 5 ms 856 KB Output isn't correct
12 Incorrect 5 ms 776 KB Output isn't correct
13 Incorrect 21 ms 2832 KB Output isn't correct
14 Incorrect 81 ms 8704 KB Output isn't correct
15 Incorrect 235 ms 18156 KB Output isn't correct
16 Incorrect 340 ms 19576 KB Output isn't correct
17 Incorrect 261 ms 21100 KB Output isn't correct
18 Incorrect 268 ms 23216 KB Output isn't correct
19 Incorrect 288 ms 25412 KB Output isn't correct
20 Incorrect 350 ms 29924 KB Output isn't correct