Submission #310811

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310811	2020-10-08T04:30:59 Z	Fischer	Schools (IZhO13_school)	C++14	75 / 100	2000 ms	13048 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2087 ms	384 KB	Time limit exceeded
2	Runtime error	3 ms	512 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Execution timed out	2087 ms	384 KB	Time limit exceeded
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Execution timed out	2078 ms	644 KB	Time limit exceeded
9	Correct	3 ms	640 KB	Output is correct
10	Correct	3 ms	640 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	23 ms	2048 KB	Output is correct
14	Correct	42 ms	3704 KB	Output is correct
15	Correct	82 ms	7672 KB	Output is correct
16	Execution timed out	2081 ms	6264 KB	Time limit exceeded
17	Correct	114 ms	9208 KB	Output is correct
18	Correct	128 ms	10616 KB	Output is correct
19	Correct	137 ms	11256 KB	Output is correct
20	Correct	157 ms	13048 KB	Output is correct