/*
Observations:
* Player takes ceil(n/2) computers, system takes floor(n/2) computers.
* Computers taken by either the player or the system form a subarray.
* After the player choose the first computer, the system can control which computers will end up for the player.
The system can do so by "copying" player's move.
With the above observation, we will take the maximum of the minimum sum of values in a segment involving the i-th computer.
*/
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, a[1000003], psum[1000003], ans;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
psum[0] = a[0];
for (int i = 1; i < 2 * n; i++) {
psum[i] = psum[i - 1] + a[i];
}
int cntTakenByPlayer = n/2 + n%2;
multiset<int> segmentSums;
ans = 0;
for (int i = 0; i + cntTakenByPlayer - 1 < 2 * n; i++) {
segmentSums.insert(psum[i + cntTakenByPlayer - 1] - (i == 0 ? 0 : psum[i - 1]));
if (i >= cntTakenByPlayer) {
int sumEndingAtPreviousIdx = psum[i - 1] - (i - 1 - cntTakenByPlayer >= 0 ? psum[i - 1 - cntTakenByPlayer] : 0);
segmentSums.erase(segmentSums.find(sumEndingAtPreviousIdx));
}
// This is important, so we don't take the wrong minimums.
// The minimums of the segments involving the earlier values will be handled in the later iterations.
if (i >= cntTakenByPlayer - 1) {
ans = max(ans, *(segmentSums.begin()));
}
}
cout << ans << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 8 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 9 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8124 KB |
Output is correct |
| 11 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 12 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 13 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 15 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 17 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8020 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 8 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 9 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8124 KB |
Output is correct |
| 11 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 12 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 13 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 15 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 17 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 19 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 20 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 21 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 22 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 23 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 24 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 25 |
Correct |
7 ms |
8140 KB |
Output is correct |
| 26 |
Correct |
6 ms |
8224 KB |
Output is correct |
| 27 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 28 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 29 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 30 |
Correct |
6 ms |
8136 KB |
Output is correct |
| 31 |
Correct |
6 ms |
8148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8016 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 4 |
Correct |
44 ms |
10252 KB |
Output is correct |
| 5 |
Correct |
127 ms |
13468 KB |
Output is correct |
| 6 |
Correct |
164 ms |
15012 KB |
Output is correct |
| 7 |
Correct |
183 ms |
16516 KB |
Output is correct |
| 8 |
Correct |
400 ms |
21964 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 5 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 6 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 7 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 8 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 9 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 10 |
Correct |
4 ms |
8124 KB |
Output is correct |
| 11 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 12 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 13 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 14 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 15 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 16 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 17 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 18 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 19 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 20 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 21 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 22 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 23 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 24 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 25 |
Correct |
7 ms |
8140 KB |
Output is correct |
| 26 |
Correct |
6 ms |
8224 KB |
Output is correct |
| 27 |
Correct |
5 ms |
8148 KB |
Output is correct |
| 28 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 29 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 30 |
Correct |
6 ms |
8136 KB |
Output is correct |
| 31 |
Correct |
6 ms |
8148 KB |
Output is correct |
| 32 |
Correct |
3 ms |
8020 KB |
Output is correct |
| 33 |
Correct |
4 ms |
8016 KB |
Output is correct |
| 34 |
Correct |
7 ms |
8148 KB |
Output is correct |
| 35 |
Correct |
44 ms |
10252 KB |
Output is correct |
| 36 |
Correct |
127 ms |
13468 KB |
Output is correct |
| 37 |
Correct |
164 ms |
15012 KB |
Output is correct |
| 38 |
Correct |
183 ms |
16516 KB |
Output is correct |
| 39 |
Correct |
400 ms |
21964 KB |
Output is correct |
| 40 |
Correct |
8 ms |
8404 KB |
Output is correct |
| 41 |
Correct |
14 ms |
8588 KB |
Output is correct |
| 42 |
Correct |
19 ms |
9032 KB |
Output is correct |
| 43 |
Correct |
126 ms |
13584 KB |
Output is correct |
| 44 |
Correct |
346 ms |
21964 KB |
Output is correct |
| 45 |
Correct |
54 ms |
10792 KB |
Output is correct |
| 46 |
Correct |
188 ms |
16452 KB |
Output is correct |
| 47 |
Correct |
405 ms |
21916 KB |
Output is correct |
| 48 |
Correct |
308 ms |
22300 KB |
Output is correct |
| 49 |
Correct |
257 ms |
21528 KB |
Output is correct |
| 50 |
Correct |
254 ms |
21424 KB |
Output is correct |
