제출 #1339628

#제출 시각아이디문제언어결과실행 시간메모리
1339628nicolo_010Art Exhibition (JOI18_art)C++20
100 / 100
208 ms27840 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const int MOD = 998244353;

struct SegTree {
	vector<ll> tree;
	SegTree(int n) {
		tree.assign(4*n, -1e18);
	}
	void query(int p, int l, int r, int i, ll x) {
		if (l>i||r<i) {
			return;
		}
		if (l==r) {
			tree[p] = x;
		}
		else {
			int m = (l+r)/2;
			query(2*p, l, m, i, x);
			query(2*p+1, m+1, r, i, x);
			tree[p] = max(tree[2*p], tree[2*p+1]);
		}
	}
	ll rmq(int p, int l, int r, int i, int j) {
		if (l>j || r<i) return -1e18;
		if (i<=l && r<=j) return tree[p];
		int m = (l+r)/2;
		return max(rmq(2*p, l, m, i, j), rmq(2*p+1, m+1, r, i, j));
	}
};

void solve() {
	int n; cin >> n;
	vector<pii> a(n);
	SegTree st(n);
	for (int i=0; i<n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a.begin(), a.end());
	vector<ll> pref(n, 0);
	pref[0] = a[0].second;
	for (int i=1; i<n; i++) {
		pref[i] = pref[i-1] + a[i].second;
	}
	for (int i=0; i<n; i++) {
		st.query(1, 0, n-1, i, pref[i]-a[i].first);
	}
	ll ans=0;
	for (int i=0; i<n; i++) {
		ll mx = st.rmq(1, 0, n-1, i, n-1);
		ll restar = (i==0 ? 0 : pref[i-1]);
		ans = max(ans, mx+a[i].first-restar);
	}
	cout << ans << "\n";
}

//1 2 3 4 0

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	while (t--) {
		solve();
	}
	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...