oj.uz

Submission #634049

# Submission time Handle Problem Language Result Execution time Memory
634049 2022-08-23T18:04:49 Z izanbf Hacker (BOI15_hac) C++14
0 / 100
 1 ms 468 KB 
#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;
	}

	/*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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 444 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -