제출 #634050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634050		izanbf	Hacker (BOI15_hac)	C++14	100 / 100	374 ms	18428 KiB

hac

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

#define D(x) cerr << #x << " = " << x << ", "

using vi = vector<int>;
using vvi = vector<vi>;

vi compute_ksums(const vi& a, int k) {
	int n = a.size();
	vi v(2*n);
	for (int i = 0; i < n; ++i) {
		v[i] = v[n+i] = a[i];
	}
	vi pre(2*n+1); // pre[i+1] = v[0]+...+v[i]
	for (int i = 0; i < 2*n; ++i) {
		pre[i+1] = pre[i] + v[i];
	}
	vi ksums(n); // ksums[i] = v[i] + ... + v[i+k-1]
	for (int i = 0; i < n; ++i) {
		ksums[i] = pre[i+k] - pre[i];
	}
	return ksums;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

	int k = n/2; // range of the deffender

	int sum = 0;
	vi v(n);
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		sum += v[i];
	}

	vi ksums = compute_ksums(v, k);
	multiset<int> s;
	int l = 1;
	int r = n-k;
	int ans = 0;
	for (int i = l; i <= r; ++i) {
		s.insert(-ksums[i]);
	} 
	for (int i = 0; i < n; ++i) {
		int best = -(*s.begin());
		ans = max(ans, sum-best);
		r = (r+1)%n;
		s.insert(-ksums[r]);
		s.erase(s.find(-ksums[l]));
		l = (l+1)%n;
	}

	/*int ans = 0;
	for (int i = 0; i < n; ++i) {
		int best = 0;
		for (int j = 0; j < n; ++j) {
			int l = j;
			int r = j+k-1;
			if ((i < l or i > r) and (n+i < l or n+i > r)) {
				best = max(best, ksums[j]);
			}
		}
		ans = max(ans, sum-best);
	}*/

	cout << ans << endl;
}

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