Submission #1226987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226987		kaiboy	Hacker (BOI15_hac)	C++20	100 / 100	32 ms	11080 KiB

hac

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 500000;

int aa[N], ss[N * 2], pp[N * 2], qq[N * 2];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	int m = (n + 1) / 2, s = 0;
	for (int i = n - m; i < n; i++)
		s += aa[i];
	for (int i = 0; i < n + m - 1; i++)
		pp[i] = qq[i] = ss[i] = s += aa[i % n] - aa[(i - m + n) % n];
	for (int i = 1; i < n + m - 1; i++)
		if (i % m)
			pp[i] = min(pp[i], pp[i - 1]);
	for (int i = n + m - 3; i >= 0; i--)
		if (i % m)
			qq[i] = min(qq[i], qq[i + 1]);
	int ans = 0;
	for (int l = 0, r = m - 1; r < n + m - 1; l++, r++)
		ans = max(ans, min(qq[l], pp[r]));
	cout << ans << '\n';
	return 0;
}

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