Submission #1270618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270618		_asunaa	Hacker (BOI15_hac)	C++20	100 / 100	189 ms	66548 KiB

hac

#include <bits/stdc++.h>
using namespace std;
long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res, arr[1500005], arr2[1500005], arr3[1500005], st[6000005];
const long long mod = 999993143, mod2 = 999993469;
string s;
bool check;
void build (long long id, long long l, long long r){
	if (l == r){
		st[id] = arr3[l];
		return;
	}
	long long mid = (l + r) >> 1;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = min(st[id * 2], st[id * 2 + 1]);
}

long long get (long long id, long long l, long long r, long long u, long long v){
	if (v < l || u > r){
		return 1e18;
	}
	if (u <= l && r <= v){
		return st[id];
	}
	long long mid = (l + r) >> 1;
	return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	arr2[0] = 0;
	for (i = 1; i <= n; i += 1){
		cin >> arr[i];
		arr[i + n] = arr[i];
		arr[i + n + n] = arr[i];
	}
	for (i = 1; i <= n * 3; i += 1){
		arr2[i] = arr2[i - 1] + arr[i];
	}
	d = (n + 1) / 2;
	for (i = 1; i + d - 1 <= n * 3; i += 1){
		arr3[i] = arr2[i + d - 1] - arr2[i - 1];
//		cout << arr3[i] << " ";
	}
//	cout << "\n";
	build(1, 1, n * 3);
	ans = 0;
	for (i = 1; i <= n; i += 1){
		ans = max(ans, get(1, 1, n * 3, i - d + 1 + n, i + n));
//		cout << i - d + 1 + n << " " << i + n << "\n";
	}
	cout << ans;
}

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