Submission #310811

#	Time	Username	Problem	Language	Result	Execution time	Memory
310811		Fischer	Schools (IZhO13_school)	C++14	75 / 100	2087 ms	13048 KiB

school

#include <bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;
using ll = long long;
struct Pair {
		int a, b, id;
} arr[maxN];
int n, m, s;
int invS[maxN], pS[maxN];
ll ds[maxN];
pair<int, ll> ft[maxN];

void update(int x, int u, int v) {
	while (x < maxN) {
		ft[x].first += u;
		ft[x].second += v;
		x += x&-x;
	}
}

ll query(int need) {
	ll ans = 0, cur = 0;
	for (int pos = 18; pos >= 0; --pos) {
		if (need >= ft[cur + (1<<pos)].first) {
			ans += ft[cur + (1<<pos)].second;
			need -= ft[cur + (1<<pos)].first;
			cur += (1<<pos);
		}
	}
	return ans;
}

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &arr[i].a, &arr[i].b);
	}
	sort(arr, arr+n, [](auto p, auto q) {
		return p.b > q.b;
	});
	for (int i = 0; i < n; ++i) {
		arr[i].id = i;
	}
	ll add = 0;
	for (int i = 0; i < s; ++i) {
		ds[i] = arr[i].a - arr[i].b;
		add += arr[i].b;
	}
	sort(ds, ds+s, greater<>());
	sort(arr, arr+n, [](auto p, auto q) {
		return p.a > q.a;
	});
	for (int i = 0, j = 0; i < n; ++i) {
		if (arr[i].id < s) continue;
		invS[arr[i].id] = ++j;
		pS[arr[i].id] = i;
		update(invS[arr[i].id], 1, arr[i].a);
	}
	priority_queue<int, vector<int>, greater<>> kSet;
	int posS = 0;
	ll ans = -1e18;
	for (int i = 0; i <= m; ++i) {
		ans = max(ans, add + query(m - i));
		auto new_element = arr[pS[s+i]];
		update(invS[s+i], -1, -new_element.a);
		add += new_element.a;
		int delta = new_element.b - new_element.a;
		while (!kSet.empty() && delta > kSet.top()) {
			if (posS >= s || ds[posS] + kSet.top() < 0) {
				add -= kSet.top();
				kSet.pop();
				posS -= 1;
				add -= ds[posS];
			} else break;
		}
		if (posS >= s) {
			if (kSet.top() < delta) {
				add += delta - kSet.top();
				kSet.pop();
				kSet.push(delta);
			}
		} else {
			if (delta + ds[posS] > 0) {
				add += delta + ds[posS++];
				kSet.push(delta);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d%d%d", &n, &m, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d%d", &arr[i].a, &arr[i].b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 75 / 100