oj.uz

Submission #431808

# Submission time Handle Problem Language Result Execution time Memory
431808 2021-06-17T15:41:52 Z Habitus Schools (IZhO13_school) C++14
25 / 100
 337 ms 73712 KB 
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, m, s;
pll x[300010];
set<pll> naja, najb, raz;
ll rez;
int main() {
    ios;
    cin >> n >> m >> s;
    for(int i=0; i<n; ++i) {
        cin >> x[i].xx >> x[i].yy;
    }
    sort(x, x+n, greater<pll>());
    for(int i=0; i<m; ++i) {
        rez+=x[i].xx;
        raz.insert({x[i].yy-x[i].xx, (ll)i});
    }
    for(int i=m; i<n; ++i) {
        naja.insert({x[i].xx, (ll)i});
        najb.insert({x[i].yy, (ll)i});
    }
    int br=0;
    while(true) {
        ++br;
        if(s==0) break;
        pll pr=*prev(najb.end());
        pll dr=*prev(raz.end());
        pll tr=*prev(naja.end());
        if(pr.xx>dr.xx+tr.xx && pr.xx>0LL) {
            rez+=pr.xx;
            --s;
            najb.erase(prev(najb.end()));
            auto it=naja.find({x[pr.yy].xx, pr.yy});
            naja.erase(it);
        }
        else if(dr.xx+tr.xx>0LL) {
            rez+=dr.xx+tr.xx;
            --s;
            raz.erase(prev(raz.end()));
            naja.erase(prev(naja.end()));
            raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy});
        }
        else break;
        if(br>=1000000) {cout << 1; break;}
    }
    cout << rez;
    return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Runtime error 1 ms 460 KB Execution killed with signal 11
5 Correct 1 ms 204 KB Output is correct
6 Runtime error 2 ms 460 KB Execution killed with signal 6
7 Runtime error 8 ms 1612 KB Execution killed with signal 11
8 Runtime error 5 ms 1100 KB Execution killed with signal 6
9 Runtime error 5 ms 1228 KB Execution killed with signal 11
10 Runtime error 4 ms 1228 KB Execution killed with signal 6
11 Runtime error 6 ms 1740 KB Execution killed with signal 6
12 Runtime error 5 ms 1868 KB Execution killed with signal 11
13 Runtime error 27 ms 6680 KB Execution killed with signal 11
14 Runtime error 87 ms 21568 KB Execution killed with signal 6
15 Correct 261 ms 22632 KB Output is correct
16 Runtime error 279 ms 48960 KB Execution killed with signal 6
17 Runtime error 235 ms 52208 KB Execution killed with signal 6
18 Runtime error 255 ms 57328 KB Execution killed with signal 6
19 Runtime error 324 ms 62952 KB Execution killed with signal 6
20 Runtime error 337 ms 73712 KB Execution killed with signal 6