Submission #334282

#	Time	Username	Problem	Language	Result	Execution time	Memory
334282		limabeans	Schools (IZhO13_school)	C++17	100 / 100	130 ms	15328 KiB

school

#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;
	} else {
	    sum += b[p2][1];
	    used[b[p2][2]]=true;
	}
    }


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

• Subtask 1: 100 / 100