Submission #696074

#	Time	Username	Problem	Language	Result	Execution time	Memory
696074		Makarooni	Hacker (BOI15_hac)	C++17	100 / 100	474 ms	22324 KiB

hac

/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 5e5 + 10;
const int MOD = 1e9 + 7;
const int inf = 1e9 + 1;
const ll INF = 3e18;

int a[N], ps[N], seg[N * 4], lz[N * 4];

void shift(int id, int s, int e){
	if(s == e)
		return;
	seg[id * 2] = min(seg[id * 2], lz[id]);
	seg[id * 2 + 1] = min(seg[id * 2 + 1], lz[id]);
	lz[id * 2] = min(lz[id], lz[id * 2]);
	lz[id * 2 + 1] = min(lz[id], lz[id * 2 + 1]);
}

void upd(int id, int s, int e, int l, int r, int x){
	shift(id, s, e);
	if(s > r || e < l)
		return;
	if(l <= s && e <= r){
		seg[id] = min(seg[id], x);
		lz[id] = min(lz[id], x);
		return;
	}
	int mid = (s + e) / 2;
	upd(id * 2, s, mid, l, r, x);
	upd(id * 2 + 1, mid + 1, e, l, r, x);
	seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}

int get(int id, int s, int e, int p){
	shift(id, s, e);
	if(s > p || e < p)
		return inf;
	if(s == e && e == p)
		return seg[id];
	int mid = (s + e) / 2;
	return min(get(id * 2, s, mid, p), get(id * 2 + 1, mid + 1, e, p));
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int t = n / 2 + (n % 2);
	for(int i = 1; i < 4 * N; i++){
		seg[i] = inf;
		lz[i] = inf;
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ps[i] = ps[i - 1] + a[i];
	}
	for(int i = 1; i <= n; i++){
		if(i >= t)
			upd(1, 1, n, i - t + 1, i, ps[i] - ps[i - t]);
		else{
			upd(1, 1, n, 1, i, ps[i] + ps[n] - ps[n - (t - i)]);
			upd(1, 1, n,  n - (t - i) + 1, n, ps[i] + ps[n] - ps[n - (t - i)]);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		ans = max(ans, get(1, 1, n, i));
	cout << ans << endl;
}

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