Submission #629731

#	Time	Username	Problem	Language	Result	Execution time	Memory
629731		heavylightdecomp	Hacker (BOI15_hac)	C++14	100 / 100	149 ms	10736 KiB

hac

#include<bits/stdc++.h>
using namespace std;
const int mxN = 2*5e5+5;
int pref[mxN], a[mxN], sig[mxN], n, k;
int rs(int i, int j) {
	if(i <= j) return pref[j] - pref[i-1];
	return rs(i, n) + rs(1, j);
}
signed main() {
	//freopen("hac.in", "r", stdin);
	//freopen("hac.out", "w", stdout);
	cin >> n;
	k = (n + 1) / 2;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) pref[i] = a[i] + pref[i-1];
	for(int i = 1; i <= n; i++) {
		if(i+k-1 <= n) sig[i] = rs(i, i+k-1);
		else sig[i] = rs(i, i+k-1-n);
	}
	for(int i = 1; i <= n; i++) sig[i+n] = sig[i];
	//for(int i = 1; i <= 2*n; i++) cerr << sig[i] << '\n';
	deque<int> st;
	int res = INT_MIN;
	for(int i = 1; i <= 2*n; i++) {
		while(st.size() and sig[i] <= sig[st.back()]) st.pop_back();
		st.push_back(i);
		while(st.size() and st.front() + k - 1 < i) st.pop_front();
		if(st.size() && i >= k) res = max(res, sig[st.front()]);
	}
	cout << res << '\n';
}

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