oj.uz

답안 #913799

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913799 2024-01-20T09:30:43 Z dsyz Hacker (BOI15_hac) C++17
0 / 100
 1 ms 2508 KB 
#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{
		swap(a,b);
		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 ptr = (N / 2) - 1 - 1;
	for(ll i = N - 1;i >= 0;i--){
		if(ptr < 0) break;
		ll sum = calc(i,ptr);
		protect.push_back({sum,{i,ptr}});
		ptr--;
	}
	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;
		//cout<<"PROTECT: "<<a<<" "<<b<<" "<<c<<'\n';
		if(a >= 1) mini[a - 1] = min(mini[a - 1],psum[N - 1] - c);
		else mini[N - 1] = min(mini[N - 1],psum[N - 1] - c);
		if(b < N - 1) mini[b + 1] = min(mini[b + 1],psum[N - 1] - c);
		else mini[0] = min(mini[0],psum[N - 1] - c);
	}
	ll maximum = 0;
	for(ll i = 0;i < N;i++){
		//cout<<"MINI: "<<mini[i]<<'\n';
		maximum = max(maximum,mini[i]);
	}
	cout<<maximum<<'\n';
}

/*
10
7 3 9 10 4 10 9 5 9 10

Correct Output: 37
7 3 9 10 "4 10 9 5 9" 10
7 3 9 10 4 10 9 5 9 10
*/

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -