Submission #967618

#	Time	Username	Problem	Language	Result	Execution time	Memory
967618		NintsiChkhaidze	Hacker (BOI15_hac)	C++17	100 / 100	205 ms	35916 KiB

hac

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
#define int ll
using namespace std;
 
const int N = 1e6 + 5,inf = 1e18;
int lz[4*N],t[4*N],p[N],a[N];
 
void build(int h,int l,int r){
	t[h] = inf;
	if (l == r) return;
	build(left);
	build(right);
}
 
void upd(int h,int l,int r,int L,int R,int vl){
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		t[h] = min(t[h],vl);
		return;
	}
	upd(left,L,R,vl);
	upd(right,L,R,vl);
}
 
int get(int h,int l,int r,int idx){
	if (l == r) return t[h];
	if (idx > (l + r)/2) return min(t[h],get(right,idx));
	return min(t[h],get(left,idx));
}
signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n;
	cin>>n;
 
	for (int i =1; i <= n; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
 
	for (int i = n + 1; i <= 2*n; i++)
		a[i] = a[i - n],p[i] = p[i - 1] + a[i];
 
	build(1,1,2*n);
	int len = (n + 1)/2;
	for (int i = 1; i <= n; i++)
		upd(1,1,2*n,i, i + len - 1,p[i + len - 1] - p[i - 1]);
	
	int ans = 0;
	for (int i = n + 1; i <= 2*n; i++)
		ans = max(ans,min(get(1,1,2*n,i),get(1,1,2*n,i - n)));
	cout<<ans;
}

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