제출 #330131

#제출 시각아이디문제언어결과실행 시간메모리
330131Kevin_Zhang_TWArt Exhibition (JOI18_art)C++17
100 / 100
214 ms16108 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> 
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	vector<pair<ll,ll>> art(n);
	for (auto &[sz, val] : art)
		cin >> sz >> val;
	art.pb(0, 0);
	sort(AI(art));

	ll mx = 0, res = 0, sum = 0;

	for (int i = 0;i <= n;++i) {
		auto [sz, val] = art[i];
		ll nxsz = i == n ? 0 : art[i+1].first;
		sum += val; 
		chmax(res, sum - sz + mx);
		chmax(mx, nxsz - sum);
		chmax(res, val);
	} 
	assert(res > 0);
	cout << res << '\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...