|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
MOG Round #25Ended |
J - Comiendo caramelos
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
Fito y Pepe se reunieron para comer dulces. Ellos tienen $N$ dulces dispuestos en una fila, y a cada uno le han asociado un valor que refleja cuan rico es. Ellos decidieron alternarse para comer, y Fito comienza. Empezando por la izquierda de la fila cada niño en su turno elige qué dulce comer, posiblemente dejando atrás algunos sin tocar, pero una vez que un dulce ha sido pasado, ninguno de los dos puede comerlo. Ellos son buenos amigos, pero también les gusta mucho comer, así que quieren maximizar el valor de los dulces que comen sin importarles cuánto coma el otro. Además, siempre elegirán comer el primer dulce que maximice este valor. Ahora ellos desean saber cuánto comerá cada cual, ayúdalos a resolver su problema.
Input
La primera línea contiene $N$ ($1 \leq N \leq 1000000$), el número de dulces que tienen.
La siguiente línea tendrá $N$ enteros $A_i$ $(1 \leq A_i \leq 100000)$, que son los valores de los dulces en orden de izquierda a derecha.
Output
Una línea con dos enteros separados por espacio, reflejando el valor de los dulces que comerán Fito y Pepe respectivamente.
Sample test(s)
Input
6
17
5
9
10
3
8
Output
27 17