Submission #913338

#	Time	Username	Problem	Language	Result	Execution time	Memory
913338		dsyz	Hacker (BOI15_hac)	C++17	0 / 100	1 ms	2396 KiB

hac

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (500005)
ll N;
ll arr[MAXN], psum[MAXN];
ll calc(ll a,ll b){
	if(a <= b){
		if(a == 0) return psum[b];
		else return psum[b] - psum[a - 1];
	}else{
		ll sum = psum[a];
		if(b == 0) sum += psum[N - 1];
		else sum += (psum[N - 1] - psum[b - 1]);
		return sum;
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N;
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
		cur += arr[i];
		psum[i] = cur;
	}
	vector<pair<ll,pair<ll,ll> > > protect;
	for(ll i = 0;i + (N / 2) - 1 < N;i++){
		ll sum = calc(i,i + (N / 2) - 1);
		protect.push_back({sum,{i,i + (N / 2) - 1}});
	}
	ll mini[N];
	for(ll i = 0;i < N;i++){
		mini[i] = psum[N - 1];
	}
	for(ll i = 0;i < ll(protect.size());i++){
		ll a = protect[i].second.first;
		ll b = protect[i].second.second;
		ll c = protect[i].first;
		if(a >= 1) mini[a - 1] = min(mini[a - 1],psum[N - 1] - c);
		if(b < N - 1) mini[b + 1] = min(mini[b + 1],psum[N - 1] - c);
	}
	ll maximum = 0;
	for(ll i = 0;i < N;i++){
		maximum = max(maximum,mini[i]);
	}
	cout<<maximum<<'\n';
}

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