제출 #481079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
481079		Sohsoh84	Hacker (BOI15_hac)	C++17	100 / 100	65 ms	10684 KiB

hac

//: // ////: ///  / : //// / :
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 1e9 + 10;

int S[MAXN], A[MAXN], n, t, ans[MAXN];
deque<pll> dq;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	t = (n + 1) / 2;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
		if (i < t) S[0] += A[i];
		ans[i] = INF;
	}

	for (int i = 1; i < n; i++)
		S[i] = S[i - 1] - A[i - 1] + A[(i + t - 1) % n];

	for (int j = 0; j < 2 * n; j++) {
		int i = j % n;
		pll e = {S[i], j};
		while (!dq.empty() && e < dq.back()) dq.pop_back();
		dq.push_back(e);

		if (j - dq.front().Y >= t) dq.pop_front();
		ans[i] = min(ans[i], dq.front().X);
	}

	cout << *max_element(ans, ans + n) << endl;
	return 0;
}

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