|
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 |
G - Juego con monedas II
Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)
Fito y Pepe se reunieron para jugar
con monedas, para esto ellos preparan una torre con N monedas y juegan
en turnos, Fito siempre comienza y puede tomar 1 o 2 monedas de la cima
de la torre. En los turnos siguientes cada jugador puede tomar entre 1 y
el doble de las monedas que tomó el jugador anterior. Fito y Pepe son
muy buenos amigos, pero también les gusta mucho ganar, así que cada uno
tratará de maximizar el valor total de las monedas que toman, sin
importarle cuánto gane el otro. Ahora Fito desea saber el valor total de
las monedas que tomará si ambos juegan de forma optima, ayudalo a
resolver su problema.
Input
La primera y única línea contendrá un entero N, cuántas monedas hay inicialmente en la torre.
La siguiente línea tendrá N enteros Ai (1 ≤ Ai ≤ 100000), que son los valores de las monedas en orden de abajo hacia arriba.
-En el primer subproblema (1 ≤ N ≤ 250)
-En el segundo subproblema (1 ≤ N ≤ 2000)
Output
Un único entero que refleja el máximo valor que podrá tomar Fito.
Sample test(s)
Input
5
1
3
1
7
2
Output
9