oj.uz

Submission #531915

# Submission time Handle Problem Language Result Execution time Memory
531915 2022-03-01T21:38:19 Z Vladth11 Schools (IZhO13_school) C++14
100 / 100
 256 ms 34480 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 300001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll nr_of_bits = 21;

pii v[NMAX];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, s, i;
    cin >> n >> m >> s;
    for(i = 1; i <= n; i++){
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    priority_queue <int> st;
    ll sol = 0;
    for(i = n; i >= n - m + 1; i--){
        sol += v[i].first;
        st.push(v[i].second - v[i].first);
    }
    multiset <pii> bestm, bests;
    for(i = n - m; i >= 1; i--){
        bestm.insert(v[i]);
        bests.insert({v[i].second, v[i].first});
    }
    for(i = 1; i <= s; i++){
        ll sterge = st.top() + (*bestm.rbegin()).first;
        ll nou = (*bests.rbegin()).first;
        if(sterge > nou){
            sol += sterge;
            pii x = *bestm.rbegin();
            bestm.erase(bestm.find(*bestm.rbegin()));
            bests.erase(bests.find({x.second, x.first}));
            st.pop();
            st.push(x.second - x.first);
        }else{
            sol += nou;
            pii x = *bests.rbegin();
            bests.erase(bests.find(*bests.rbegin()));
            bestm.erase(bestm.find({x.second, x.first}));
        }
    }
    cout << sol;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 300 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 332 KB Output is correct
7 Correct 4 ms 844 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 4 ms 972 KB Output is correct
12 Correct 4 ms 1024 KB Output is correct
13 Correct 11 ms 1928 KB Output is correct
14 Correct 76 ms 11036 KB Output is correct
15 Correct 179 ms 24276 KB Output is correct
16 Correct 256 ms 24920 KB Output is correct
17 Correct 159 ms 23480 KB Output is correct
18 Correct 201 ms 25648 KB Output is correct
19 Correct 190 ms 28636 KB Output is correct
20 Correct 240 ms 34480 KB Output is correct