제출 #1332848

#제출 시각아이디문제언어결과실행 시간메모리
1332848gelastropodArt Exhibition (JOI18_art)C++20
100 / 100
234 ms16296 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 = 0; i < u.size(); i++) {
		crntmax = max(crntmax, u[i] - thin[i]);
		ans = max(ans, thin[i + 1] - u[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...