Submission #1242643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242643		g4yuhg	Art Exhibition (JOI18_art)	C++20	100 / 100	177 ms	16160 KiB

art

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define TASK "mroads"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 500006
using namespace std;

bool ghuy4g;

ll n, a[N], b[N], pf[N];

vector<ll> nenSo;

void solve() {
	ll ans = 0;
	ll mini = 0;
	mini = min(mini, pf[0] - nenSo[0]);
	for (int i = 1; i <= nenSo.size(); i ++) {
		ans = max(ans, pf[i] - nenSo[i - 1] - mini);
		if (i < nenSo.size()) {
			mini = min(mini, pf[i] - nenSo[i]);
		}
	}
	cout << ans;
}

bool klinh;

signed main(void) {
	faster;
	
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i] >> b[i];
		nenSo.push_back(a[i]);
	}
	sort(nenSo.begin(), nenSo.end());
	nenSo.resize(unique(nenSo.begin(), nenSo.end()) - nenSo.begin());
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(nenSo.begin(), nenSo.end(), a[i]) - nenSo.begin() + 1;
		pf[a[i]] += b[i];
	}
	for (int i = 1; i <= nenSo.size(); i ++) {
		pf[i] += pf[i - 1];
	}
	
	solve();
	
	cerr << fabs(&ghuy4g - &ghuy4g) / 1048576.0;
	return 0;
}

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