Submission #727494

#	Time	Username	Problem	Language	Result	Execution time	Memory
727494		AdamGS	Hacker (BOI15_hac)	C++17	100 / 100	104 ms	8720 KiB

hac

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7, INF=1e9+7;
int tr[4*LIM], T[LIM], n, N=1;
int cnt(int l, int r) {
	if(l>r) return INF;
	l+=N; r+=N;
	int ans=min(tr[l], tr[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=min(ans, tr[l+1]);
		if(r%2==1) ans=min(ans, tr[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
int ile(int x) {
	int y=(x+(n+1)/2-1)%n;
	if(y<x) return min(cnt(x, n-1), cnt(0, y));
	return cnt(x, y);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	while(N<n) N*=2;
	rep(i, n) cin >> T[i];
	rep(i, (n+1)/2) tr[N]+=T[i];
	rep(i, n-1) tr[N+i+1]=tr[N+i]+T[((n+1)/2+i)%n]-T[i];
	for(int i=N-1; i>=0; --i) tr[i]=min(tr[2*i], tr[2*i+1]);
	int ans=0;
	rep(i, n) ans=max(ans, ile(i));
	cout << ans << '\n';
}

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