Submission #335371

#	Time	Username	Problem	Language	Result	Execution time	Memory
335371		AQT	Art Exhibition (JOI18_art)	C++17	100 / 100	251 ms	24816 KiB

art

#include <bits/stdc++.h>

using namespace std;

int N;
pair<long long, long long> arr[500005];
long long pre[500005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i<=N; i++){
		cin >> arr[i].first >> arr[i].second;
	}
	sort(arr+1, arr+1+N);
	for(int i = 1; i<=N; i++){
		pre[i] = pre[i-1] + arr[i].second;
	}
	long long mn = LLONG_MAX/4;
	long long ans = 0;
	for(int i = 1; i<=N; i++){
		mn = min(mn, - arr[i].first + pre[i-1]);
		ans = max(ans, pre[i] - arr[i].first - mn);
	}
	cout << ans << "\n";
}

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