Submission #634036

#	Time	Username	Problem	Language	Result	Execution time	Memory
634036		izanbf	Hacker (BOI15_hac)	C++14	40 / 100	1074 ms	2796 KiB

hac

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

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

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

struct SparseTable {
	const int J = 20;
	const int OP_NULL = 1.01e9;
	vvi st;
	vi lg;
	int n;

	int op(int a, int b) const { return min(a, b); }

	int query(int l, int r) const {
		if (l > r or l < 0 or r >= n)
			return OP_NULL;
		int j = lg[r-l+1];
		return op(st[j][l], st[j][r-(1<<j)+1]);
	}

	SparseTable(const vi& a) {
		n = a.size();
		lg = vi(n+1);
		lg[1] = 0;
		for (int i = 2; i <= n; ++i)
			lg[i] = 1 + lg[i/2];
		st = vvi(J, vi(n));
		for (int i = 0; i < n; ++i)
			st[0][i] = a[i];
		for (int j = 1; j < J; ++j)
			for (int i = 0; i+(1<<j)-1 < n; ++i)
				st[j][i] = op(st[j-1][i], st[j-1][i+(1<<(j-1))]);
	}
};

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);
	reverse(v.begin(), v.end());
	vi rev_ksums = compute_ksums(v, k);

	/*SparseTable st(ksums);
	SparseTable rst(rev_ksums);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		int best = max(st.query(i+1, n+i-k), rst.query(n-1-(n+i-k), n-1-(i+1)));
		ans = max(ans, sum-best);
	}*/

	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: 0 / 20
• Subtask 4: 0 / 40