제출 #1270609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270609		tryharderforioi100	Hacker (BOI15_hac)	C++17	100 / 100	161 ms	30628 KiB

hac

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
ll segtree[4000020];
ll pf[1000005];
void build(ll id,ll l,ll r)
{
	if(l==r)
	{
		segtree[id]=pf[l];
		return;
	}
	ll mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	segtree[id]=max(segtree[id*2],segtree[id*2+1]);
}
ll get(ll id,ll l,ll r,ll u,ll v)
{
	if(r<u||l>v)
	{
		return 0;
	}
	if(u<=l&&r<=v)
	{
		return segtree[id];
	}
	ll mid=(l+r)/2;
	return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t=1;
	//cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll a[2*n+1],i,tong=0;
		a[0]=0;
		for(i=1;i<=n;i++)
		{
			cin>>a[i];
			tong+=a[i];
			a[i+n]=a[i];
		}
		ll len=n/2,tong1=0;
		for(i=1;i<=2*n;i++)
		{
			tong1+=a[i];
			if(i<len)
			{
				continue;
			}
			if(i==len)
			{
				pf[i]=tong1;
				continue;
			}
			pf[i]=pf[i-1]+a[i]-a[i-len];
			//cout<<pf[i]<<endl;
		}
		build(1,1,2*n);
		ll val=1e18;
		for(i=1;i<=n;i++)
		{
			//cout<<get(1,1,2*n,i+1,i+n-1)<<endl;
			val=min(val,get(1,1,2*n,i+len,i+n-1));
		}
		cout<<tong-val<<endl;
	}
	#ifndef ONLINE_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	#endif
	return 0;
}
// Author: tryharderforioi100

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