Submission #197027

#	Time	Username	Problem	Language	Result	Execution time	Memory
197027		Juney	Art Exhibition (JOI18_art)	C++14	100 / 100	298 ms	24708 KiB

art

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5 + 5;

int N;
ll A[MAXN], V[MAXN], S[MAXN], ans;
pll in[MAXN];

void f(int s, int e, int l, int r) {
	if(r < l) return;
	int mid = l + r >> 1;
	int k = -1;
	ll val = 0;
	for(int i=max(s, mid); i<=e; i++) {
		if(val < S[i] - S[mid-1] - A[i] + A[mid]) {
			val = S[i] - S[mid-1] - A[i] + A[mid];
			k = i;
		}
	}
	ans = max(ans, val);
	f(s, k, l, mid-1); f(k, e, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for(int i=1; i<=N; i++) cin >> in[i].fi >> in[i].se;
	sort(in+1, in+1+N);
	for(int i=1; i<=N; i++) A[i] = in[i].fi, V[i] = in[i].se, S[i] = S[i-1] + V[i];
	f(1, N, 1, N);
	cout << ans;
}

Compilation message (stderr)

art.cpp: In function 'void f(int, int, int, int)':
art.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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