ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2000. Grand Theft Array V

Hint
Posted by Nivranshu 24 May 2016 14:45
To play optimally, both players would first move towards each other and then from the point of their intersection they will take all the numbers from that point to their nearest boundaries.
Let Player 1 start from X and Player 2 start from Y.
Then,
if (X < Y), player 1 will take all the numbers from A[1] to A[X] and player 2 will take all the numbers from A[Y] to A[N] and also player 1 will take the numbers from A[X] to A[(X+Y)/2] and player 2 will take the numbers from A[(X+Y)/2+1] to A[Y].
if (X > Y) same as above but now player 1 will work from X to N and player 2 will work from 1 to Y.
if (X == Y), calculate the sum from A[1] to A[X-1] and another sum from A[X+1] to A[N],
add A[X] to the greater sum and give it to player 1.