Submission #1192284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192284		_rain_	Hacker (BOI15_hac)	C++20	100 / 100	56 ms	16964 KiB

hac

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

const int N=(int)5e5;
LL sum[N*2+2]={},a[N*2+2]={};
int n;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
//	freopen("main.inp","r",stdin);
	
	cin>>n;
	int slide=(n+1)/2;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=n+1;i<=n*2;++i) a[i]=a[i-n];
	for(int i=1;i<=n*2;++i) sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;++i) a[i]=sum[i+slide-1]-sum[i-1];
	for(int i=n+1;i<=n*2;++i) a[i]=a[i-n];
	deque<int>q;
	for(int i=1;i<=n;++i){
		while (q.size() && a[q.back()]>=a[i]) q.pop_back();
		q.push_back(i);
	}
	LL ans=0;
	for(int i=n+1;i<=n*2;++i){
		while (q.size() && q.front() < i-slide+1) q.pop_front();
		while (q.size() && a[q.back()] >= a[i]) q.pop_back();
		q.push_back(i);
		ans=max(ans,a[q.front()]);
	}

	cout<<ans;
}

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