제출 #330131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330131		Kevin_Zhang_TW	Art Exhibition (JOI18_art)	C++17	100 / 100	214 ms	16108 KiB

art

#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';
}

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