Submission #652151

#	Time	Username	Problem	Language	Result	Execution time	Memory
652151		ymm	Hacker (BOI15_hac)	C++17	100 / 100	133 ms	10576 KiB

hac

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500'010;
int seg[2*N];

const int inf = 1e9+10;

void up(int l, int r, int x)
{
	l += N;
	r += N;
	while (l < r) {
		if (l&1) {
			seg[l] = min(seg[l], x);
			++l;
		}
		if (r&1) {
			--r;
			seg[r] = min(seg[r], x);
		}
		l /= 2;
		r /= 2;
	}
}

int get(int i)
{
	i += N;
	int ans = inf;
	while (i) {
		ans = min(ans, seg[i]);
		i /= 2;
	}
	return ans;
		
}

int n;
int a[N];
int pre[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	fill(seg, seg+2*N, inf);
	cin >> n;
	Loop (i,0,n) {
		cin >> a[i];
		pre[i+1] = pre[i] + a[i];
	}
	int len = (n+1)/2;
	Loop (i,0,n) {
		if (i+len <= n) {
			int sum = pre[i+len] - pre[i];
			up(i, i+len, sum);
		} else {
			int sum = pre[n] - pre[i] + pre[i+len-n];
			up(i, n, sum);
			up(0, i+len-n, sum);
		}
	}
	int ans = 0;
	Loop (i,0,n)
		ans = max(ans, get(i));
	cout << ans << '\n';
}

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