제출 #241334

#제출 시각아이디문제언어결과실행 시간메모리
241334cstuartArt Exhibition (JOI18_art)C++17
100 / 100
234 ms20308 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...