Submission #241334

#	Time	Username	Problem	Language	Result	Execution time	Memory
241334		cstuart	Art Exhibition (JOI18_art)	C++17	100 / 100	234 ms	20308 KiB

art

#define _USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 1000000007ll
#define INF 1000000000000000000ll
#define EPS 1e-9
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll TC, N, P[500005], R, M;
vector <pl> art;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	TC = 1;
	
	for (ll tc = 1; tc <= TC; tc++) {
		
		cin >> N;
		art.emplace_back(0, 0);
		for (ll i = 1; i <= N; i++) {
			ll a, b;
			cin >> a >> b;
			art.emplace_back(a, b);
		}
		sort(art.begin(), art.end());
		
		P[0] = 0;
		for (ll i = 1; i <= N; i++) {
			P[i] = P[i-1] + art[i].second;
		}
		
		M = 0;
		R = INF;
		for (ll i = 1; i <= N; i++) {
			R = min(R, P[i-1] - art[i].first);
			M = max(M, P[i] - art[i].first - R);
		}
		
		cout << M << "\n";
		
	}
	
    return 0;
}

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