제출 #914132

#제출 시각아이디문제언어결과실행 시간메모리
914132lamterArt Exhibition (JOI18_art)C++17
100 / 100
178 ms27036 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...