Submission #256616

#	Time	Username	Problem	Language	Result	Execution time	Memory
256616		super_j6	Hacker (BOI15_hac)	C++14	100 / 100	80 ms	18808 KiB

hac

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, ll>
#define f first
#define s second

struct mque{
	stack<pi> s1, s2;
	
	ll mn(stack<pi> &s){
		return s.empty() ? 0x3f3f3f3f3f3f3f3f : s.top().s;
	}
	
	void add(ll x){
		s1.push({x, min(x, mn(s1))});
	}
	
	void del(){
		if(s2.empty()) for(; !s1.empty(); s1.pop()) s2.push({s1.top().f, min(s1.top().f, mn(s2))});
		s2.pop();
	}
	
	ll qry(){
		return min(mn(s1), mn(s2));
	}
};

const int mxn = 1500001;
int n;
ll a[mxn];
mque q;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(int j = 1; j < 3; j++) a[j * n + i] = a[i];
		a[i] += a[i - 1];
	}
	
	ll ret = 0;
	for(int i = n + 1; i <= 3 * n; i++){
		a[i] += a[i - 1];
		q.add(a[i] - a[i - (n + 1) / 2]);
		if(i - n > (n + 1) / 2) q.del(), ret = max(ret, q.qry());
	}
	
	cout << ret << endl;

	return 0;
}

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