Submission #1270670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270670		BuzzyBeez	Hacker (BOI15_hac)	C++20	100 / 100	142 ms	60488 KiB

hac

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

const long long inf = 1e18;

int a[1500008];
long long pf[1500008], b[1500008];

struct Segment_Tree {
	int tree_size(int m) {return 1 << (__lg(m - 1) + 2);}
	
	int n;
	vector<long long> node;
	
	void init(int m) {
		n = m;
		node.assign(tree_size(n) + 8, 0);
	}
	
	void build(int id, int l, int r, long long* arr) {
		if (l == r) {node[id] = arr[l]; return;}
		int mid = (l + r) / 2;
		build(id * 2, l, mid, arr);
		build(id * 2 + 1, mid + 1, r, arr);
		node[id] = min(node[id * 2], node[id * 2 + 1]);
	}
	
	long long query(int id, int l, int r, int u, int v) {
		if (r < u || v < l) return inf;
		if (u <= l && r <= v) return node[id];
		int mid = (l + r) / 2;
		return min(query(id * 2, l, mid, u, v), query(id * 2 + 1, mid + 1, r, u, v));
	}
	
	long long query(int l, int r) {return query(1, 1, n, l, r);}
} tree;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[n + n + i] = a[n + i] = a[i];
	}
	int len = (n + 1) / 2;
	for (int i = 1; i <= n * 3; ++i) pf[i] = pf[i - 1] + a[i];
	for (int i = 1; i <= n * 3; ++i) if (i >= len) b[i] = pf[i] - pf[i - len];
	tree.init(n * 3); tree.build(1, 1, n * 3, b);
	long long ans = 0;
	for (int i = n + 1; i <= n + n; ++i) ans = max(ans, tree.query(i, i + len - 1));
	cout << ans;
}

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