Submission #1114490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114490		Tsagana	Schools (IZhO13_school)	C++14	10 / 100	333 ms	18076 KiB

school

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
#define sp << ' ' <<
#define nl << '\n'

using namespace std;

vector<pair<int, int>> vx;
vector<pair<int, int>> vy;
vector<pair<int, int>> v;
queue<int> q;
int has[300001];

bool cmp(pair<int, int> a, pair<int, int> b) {return (a.F < b.F ? 0 : 1);}

void solve () {
	int n, m, s; cin >> n >> m >> s;

	for (int i = 0; i < n; i++) {
		int x, y; cin >> x >> y;
		v.pb({x, y});
		vx.pb({x, i});
		vy.pb({y, i});
	}
	sort(all(vx), cmp);
	sort(all(vy), cmp);

	int ans = 0, lx = m, ly = s;
	for(int i = 0; i < m; i++) {
		ans += vx[i].F;
		has[vx[i].S]++;
	}
	for(int i = 0; i < s; i++) {
		ans += vy[i].F;
		has[vy[i].S]++;
		if (has[vy[i].S] == 2) q.push(vy[i].S);
	}

	while(!q.empty()) {
		int i = q.front(); q.pop();

		while (lx < n && has[vx[lx].S]) lx++;
		while (ly < n && has[vy[ly].S]) ly++;

		int d1 = v[i].F - vx[lx].F;
		int d2 = v[i].S - vy[ly].F;

		if (lx == n || d1 <= d2) {
			ans -= d1;
			has[vy[ly].S] = 1;
			continue ;
		}
		if (ly == n || d2 <= d1) {
			ans -= d2;
			has[vx[lx].S] = 1;
			continue ;
		}
	}
	cout << ans;
}
int main() {IOS solve(); return 0;}

• Subtask 1: 10 / 100