Submission #751108

#	Time	Username	Problem	Language	Result	Execution time	Memory
751108		vjudge1	Art Exhibition (JOI18_art)	C++17	100 / 100	223 ms	24744 KiB

art

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll N;

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

	cin >> N;
	vector<pair<ll, ll>> v;
	v.push_back({0, 0});
	for(int i = 0; i < N; i++) {
		ll w, x;
		cin >> w >> x;
		v.push_back({w, x});
	}
	
	sort(v.begin(), v.end());

	vector<ll> pref(N + 1);
	for(int i = 1; i <= N; i++) pref[i] = pref[i - 1] + v[i].second;
	for(int i = 0; i < N; i++) pref[i] -= v[i + 1].first;

	ll opt = pref[0], s = 0, ans = 0;
	for(int i = 1; i <= N; i++) {
		s += v[i].second;
		ans = max(ans, s - opt - v[i].first);
		opt = min(opt, pref[i]);
	}

	cout << ans << '\n';
}

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