oj.uz

Submission #651147

# Submission time Handle Problem Language Result Execution time Memory
651147 2022-10-17T12:21:32 Z alvinpiter Hacker (BOI15_hac) C++14
0 / 100
 4 ms 8020 KB 
/*
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 < 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));
    }

    ans = max(ans, *(segmentSums.begin()));
  }

  cout << ans << endl;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Incorrect 4 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Incorrect 4 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Incorrect 4 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8020 KB Output is correct
2 Incorrect 4 ms 8020 KB Output isn't correct
3 Halted 0 ms 0 KB -