Submission #1128013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128013		Halym2007	Hacker (BOI15_hac)	C++17	100 / 100	226 ms	28456 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int NN = 1e6 + 5;
ll n, p[NN], a[NN], sum, st[NN * 4];

void update (int idx, int x, int y, int l, ll r) {
	if (x == y) {
		st[idx] = r;
		return;
	}
	int mid = (x + y) / 2;
	if (l <= mid)
		update (idx * 2, x, mid, l, r);
	else
		update (idx * 2 + 1, mid + 1, y, l, r);
	st[idx] = max (st[idx * 2], st[idx * 2 + 1]);
}

void jogap (int idx, int x, int y, int l, int r) {
	if (l <= x and y <= r) {
		sum = max (st[idx], sum);
		return;
	}
	if (l > y or x > r) return;
	int mid = (x + y) / 2;
	jogap (idx * 2, x, mid, l, r);
	jogap (idx * 2 + 1, mid + 1, y, l, r);
}


int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i + n] = a[i];
	}
	for (int i = 1; i <= 2 * n; ++i) {
		p[i] = p[i - 1] + a[i];
	}
	int ope = n / 2;
	for (int i = 1; i <= 2 * n; ++i) {
		if (i + ope - 1 > 2 * n) break;
		update (1, 1, 2 * n, i, p[i + ope - 1] - p[i - 1]);
	}
	ll mx = 0, jog = 0;
	for (int i = 1; i <= n; ++i) {
		ll jog = 0;
		sum = 0;
		jogap (1, 1, 2 * n, i + 1,  (n + i - 1) - ope + 1);
		jog = max (jog, sum);		
		mx = max (mx, p[n] - jog);
	} 
	cout << mx;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40