Submission #914132

#	Time	Username	Problem	Language	Result	Execution time	Memory
914132		lamter	Art Exhibition (JOI18_art)	C++17	100 / 100	178 ms	27036 KiB

art

#include <bits/stdc++.h>
using i64 = long long int;

int main(void) {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(nullptr);

	int n; std::cin >> n;
	std::vector <i64> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i += 1) {
		std::cin >> b[i] >> a[i];
	}
	std::vector <int> ord(n + 1); std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin() + 1, ord.end(), [&] (int i, int j) -> bool { return b[i] < b[j]; });
	std::vector <i64> p(n + 1);
	for (int i = 1; i <= n; i += 1) {
		p[i] = p[i - 1] + a[ord[i]];
	}
	i64 ans = 0;
	i64 mi = p[0] - b[ord[1]];
	for (int i = 1; i <= n; i += 1) {
		ans = std::max(ans, p[i] - b[ord[i]] - mi);
		if (i + 1 <= n)
			mi = std::min(mi, p[i] - b[ord[i + 1]]);
	}
	std::cout << ans << '\n';

	return 0^0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50