Submission #655083

#	Time	Username	Problem	Language	Result	Execution time	Memory
655083		as111	Schools (IZhO13_school)	C++17	15 / 100	210 ms	14976 KiB

school

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#define MAXN 300000
#define s second
#define f first

using namespace std;
int cities[MAXN + 1][2];
bool used[MAXN + 1]; // city used or not
vector<pair<int, pair<int, int>>> music;
vector<pair<int, pair<int, int>>> sports;
int N;
int mpos = N - 1;
int spos = N - 1;
void findM() {
	while (used[music[mpos].s.s] && mpos != 0) mpos--;
}
void findS() {
	while (used[sports[spos].s.s]) spos--;
}
int main() {
	int M, S;
	cin >> N >> M >> S;
	for (int i = 0; i < N; i++) {
		cin >> cities[i][0] >> cities[i][1];
		music.push_back(make_pair(cities[i][0], make_pair(cities[i][1], i)));
		sports.push_back(make_pair(cities[i][1], make_pair(cities[i][0], i)));
	}
	sort(music.begin(), music.end());
	sort(sports.begin(), sports.end());
	int ans = 0;
	mpos = N - 1;
	spos = N - 1;
	while (M > 0) {
		used[music[mpos].s.s] = true;
		ans += music[mpos].f;
		findM();
		M--;
	}
	while (S > 0) {
		int pos = sports[spos].s.s;
		if (used[pos]) {
			findM();
			if (cities[pos][1]+music[mpos].f > cities[pos][0]) {
				ans += cities[pos][1] + music[mpos].f - cities[pos][0];
				used[music[mpos].s.s] = true;
				spos--;
				S--;
			}
			else {
				spos--;
			}
		}
		else {
			ans += sports[spos].f;
			used[sports[spos].s.s] = true;
			spos--;
			S--;
		}
	}
	cout << ans;
}

• Subtask 1: 15 / 100