Submission #78534

#	Time	Username	Problem	Language	Result	Execution time	Memory
78534		Origims	Art Exhibition (JOI18_art)	C++14	100 / 100	257 ms	222916 KiB

art

// In The Name Of God
#include <bits/stdc++.h>

#define sqr(A) ((A) * (A))
#define F first
#define S second
#define MP make_pair
#define bsz  __builtin_popcount
#define all(A) A.begin(), A.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int PR = 727;
const int INF = INT_MAX;
const ll LINF = LLONG_MAX;

const int N = 5e5 + 20;
pii a[N];
ll n, ans;

void solve(int l, int r) {
	if (r - l < 2) {
		ans = max(ans, a[l].S);
		return ;
	}
	int mid = (l + r) / 2;
	solve(l, mid);
	solve(mid, r);
	ll sum = 0, res = 0;
	for (int i = mid - 1; i >= l; i--) {
		sum += a[i].S;
		res = max(res, sum - (a[mid].F - a[i].F));
	}
	sum = 0;
	for (int i = mid; i < r; i++) {
		sum += a[i].S;
		ans = max(ans, sum - (a[i].F - a[mid].F) + res);
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].F >> a[i].S;
	sort(a, a + n);
	solve(0, n);
	cout << ans << endl;
}

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