ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Regional School Programming Contest 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Grand Theft Array V

Time limit: 0.5 second
Memory limit: 64 MB
A long anticipated game called Grand Theft Array V is about to appear in shops! What, haven’t you heard of it? Then we must tell you all about it!
The gameplay in GTA V takes place on a one-dimensional array of integers. The game has two players, each player has his own specified starting position. Players move in turns. During each turn a player takes a number written in his current cell, then writes a zero in it and moves to the left or right adjacent cell. Naturally, the player cannot move beyond the boundaries of the array. At some moment of time two players can be located in the same cell. A player’s score is the sum of all numbers he earns during the game. The game ends when zeroes are written in all cells of the array.
Now please calculate the maximum number of points the first and the second player can get (the first player moves first, naturally), if they play optimally well, that is, if they try to maximize their score and if there are multiple variants of maximizing one’s own score, they try to minimize the opponent’s score.


The first line contains an integer n that is the size of array (10 ≤ n ≤ 105). The second line contains n integers representing the initial array. All elements of the array are non-negative and do not exceed 10 000. The third line contains two integers that are the starting positions of the first and the second player, correspondingly. The cells of the array are indexed starting from one.


Output the score of the first and the second player correspondingly if both play optimally well.


1 2 3 4 5 6 7 8 9 0
4 8
21 24
Problem Author: Ilya Kuchumov. (Prepared by Kirill Devyatkin)
Problem Source: Ural Regional School Programming Contest 2013
To submit the solution for this problem go to the Problem set: 2000. Grand Theft Array V