oj.uz

Submission #334281

# Submission time Handle Problem Language Result Execution time Memory
334281 2020-12-08T23:01:09 Z limabeans Schools (IZhO13_school) C++17
10 / 100
 151 ms 15328 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;

const ll inf = 1e18;

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<ll> 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]);
    }

    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++;

	ll gain = -inf;
	if (!pq.empty()) {
	    gain = pq.top();
	}

	if (gain+a[p1][0]>b[p2][1]) {
	    pq.pop();
	    sum += gain+a[p1][0];
	    pq.push(a[p1][1]-a[p1][0]);
	    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 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 0 ms 364 KB Output isn't correct
6 Incorrect 1 ms 364 KB Output isn't correct
7 Incorrect 2 ms 492 KB Output isn't correct
8 Incorrect 2 ms 620 KB Output isn't correct
9 Incorrect 3 ms 620 KB Output isn't correct
10 Incorrect 2 ms 620 KB Output isn't correct
11 Incorrect 2 ms 620 KB Output isn't correct
12 Incorrect 3 ms 620 KB Output isn't correct
13 Incorrect 19 ms 2416 KB Output isn't correct
14 Incorrect 33 ms 4204 KB Output isn't correct
15 Incorrect 68 ms 7788 KB Output isn't correct
16 Incorrect 84 ms 9068 KB Output isn't correct
17 Incorrect 99 ms 11364 KB Output isn't correct
18 Incorrect 106 ms 12520 KB Output isn't correct
19 Incorrect 113 ms 13412 KB Output isn't correct
20 Incorrect 151 ms 15328 KB Output isn't correct