Submission #651147

#	Time	Username	Problem	Language	Result	Execution time	Memory
651147		alvinpiter	Hacker (BOI15_hac)	C++14	0 / 100	4 ms	8020 KiB

hac

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