oj.uz

Submission #913338

# Submission time Handle Problem Language Result Execution time Memory
913338 2024-01-20T07:29:26 Z dsyz Hacker (BOI15_hac) C++17
0 / 100
 1 ms 2396 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{
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -