oj.uz

Submission #334279

# Submission time Handle Problem Language Result Execution time Memory
334279 2020-12-08T22:56:11 Z limabeans Schools (IZhO13_school) C++17
10 / 100
 137 ms 19548 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;






int n, m, s;
vector<array<ll,3>> a;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m>>s;
    a.resize(n);
    for (int i=0; i<n; i++) {
	cin>>a[i][0]>>a[i][1];
    }

    sort(a.rbegin(),a.rend());
    for (int i=0; i<n; i++) {
	a[i][2]=i;
    }

    vector<bool> used(n, false);
    priority_queue<pair<ll,int>> pq;

    ll sum = 0;
    for (int i=0; i<m; i++) {
	sum += a[i][0];
	used[a[i][2]] = true;
	pq.push({a[i][1]-a[i][0],a[i][2]});
    }

    auto b = a;
    sort(b.begin(),b.end(),[&](array<ll,3> x, array<ll,3> y) {
	    return x[1]<y[1];
	});
    reverse(b.begin(),b.end());

    int p1=0;
    int p2=0;

    for (int z=0; z<s; z++) {
	while (p1<n && used[a[p1][2]]) p1++;
	while (p2<n && used[b[p2][2]]) p2++;
	auto cur = pq.top();
	ll gain = cur.first;
	
	if (gain+a[p1][0]>b[p2][1]) {
	    pq.pop();
	    sum += gain+a[p1][0];
	    pq.push({a[p1][1]-a[p1][0],a[p1][2]});
	    used[a[p1][2]]=true;
	    used[b[p2][2]]=true;
	} else {
	    sum += b[p2][1];
	    used[b[p2][2]]=true;
	}
    }


    cout<<sum<<endl;    
    return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 2 ms 620 KB Output isn't correct
8 Runtime error 3 ms 1132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 3 ms 748 KB Output isn't correct
10 Incorrect 3 ms 748 KB Output isn't correct
11 Incorrect 3 ms 620 KB Output isn't correct
12 Incorrect 3 ms 620 KB Output isn't correct
13 Incorrect 17 ms 3060 KB Output isn't correct
14 Incorrect 35 ms 5104 KB Output isn't correct
15 Incorrect 71 ms 9580 KB Output isn't correct
16 Incorrect 87 ms 11240 KB Output isn't correct
17 Incorrect 109 ms 14688 KB Output isn't correct
18 Incorrect 132 ms 16100 KB Output isn't correct
19 Incorrect 119 ms 17120 KB Output isn't correct
20 Incorrect 137 ms 19548 KB Output isn't correct