Submission #1332841

#TimeUsernameProblemLanguageResultExecution timeMemory
1332841gelastropodArt Exhibition (JOI18_art)C++20
0 / 100
1 ms344 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, a, b, csum = 0, prev = -1, crntmax = INT_MIN, ans = 0; cin >> N;
	vector<pair<int, int>> vals;
	vector<int> u;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		vals.push_back({ a, b });
		u.push_back(a);
	}
	sort(u.begin(), u.end());
	u.erase(unique(u.begin(), u.end()), u.end());
	for (int i = 0; i < N; i++) vals[i].first = lower_bound(u.begin(), u.end(), vals[i].first) - u.begin();
	sort(vals.begin(), vals.end());
	vector<int> thin((int)u.size() + 1, 0);
	for (int i = 0; i < N; i++) {
		csum += vals[i].second;
		thin[vals[i].first + 1] = csum;
	}
	for (int i = (int)u.size() - 1; i >= 0; i--) {
		crntmax = max(crntmax, thin[i + 1] - u[i]);
		ans = max(ans, u[i] - thin[i] + crntmax);
	}
	cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...