Submission #696093

#	Time	Username	Problem	Language	Result	Execution time	Memory
696093		Kahou	Hacker (BOI15_hac)	C++14	100 / 100	73 ms	41788 KiB

hac

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 5e5 + 50, LG = 20;
int n, a[N], sum, s[N], sp[LG][N];

int get(int l, int r) {
	int k = 31-__builtin_clz(r-l+1);
	return max(sp[k][l], sp[k][r-(1<<k)+1]);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	for (int i = 1; i <= 2*n; i++) {
		s[(i-1)%n+1] = s[(i-2)%n+1] + a[(i-1)%n+1];
		if (i > n/2) s[(i-1)%n+1] -= a[(i-n/2-1)%n+1];
	}
	for (int i = 1; i <= n; i++) {
		sp[0][i] = s[i];
	}
	for (int k = 1; k < LG; k++) {
		for (int i = 1; i <= (n-(1<<k)+1); i++) {
			sp[k][i] = max(sp[k-1][i], sp[k-1][i+(1<<(k-1))]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (i + n/2 > n) {
			ans = max(ans, sum-get((i+(n/2)-1)%n+1, i-1));
		}
		else {
			ans = max(ans, sum-max((i > 1? get(1, i-1):0), get(i+(n/2), n)));
		}
	}
	cout << ans << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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