Salto de desaceleración

Points: 100

Time limit: 3.0s

Memory limit: 256M

Author:

leocar

Problem type

Allowed languages

C++, Python

Un atleta participa en un nuevo deporte que es la mezcla perfecta entre la tataracha (rayuela) y el triple salto. Para este deporte el jurado, coloca $n$ ~n~ cuadrados en el suelo en línea, con distancias iguales entre ellos. La primera fase es la aproximación, en la que un atleta hacia el primer cuadrado, inicia el primer salto. A continuación, puede saltar en cualquier otro cuadrado, y finalmente debe aterrizar en el último cuadrado.

El jurado ha dado un número predeterminado de puntos a los saltos en cada casilla, y la puntuación del atleta será la suma de las puntuaciones de todas las casillas en las que salte, incluidas la primera y la última.

Debido a la naturaleza de este deporte, una vez que el atleta comienza a saltar, no puede acelerar más, y la longitud de los saltos consecutivos nunca puede aumentar. Naturalmente, también es imposible invertir la dirección.

Taraea

Teniendo en cuenta los puntos que el jurado ha asignado a cada casilla, encuentra la máxima puntuación posible que un atleta puede obtener en esta prueba.

Entrada

La entrada consiste en:

Una línea con un número entero $n$ ~n~ $(2 \le n \le 3000)$ ~(2 \le n \le 3000)~, el número de casillas.
Una línea con n enteros $p_1, p_2, ..., p_n$ ~p_1, p_2, ..., p_n~ $(-109 \le p_i \le 10^9)$ ~(-109 \le p_i \le 10^9)~, el número de puntos que el jurado otorga por saltar en cada una de las casillas.

Salida

Impirma la puntuación máxima que puede obtener un atleta.

Ejemplo #1 de Entrada

4
1 -1 1 1

Ejemplo #1 de Salida

Ejemplo #2 de Entrada

4
1 1 -1 1

Ejemplo #2 de Salida

Ejemplo #3 de Entrada

3
-1 -1 1

Ejemplo #3 de Salida

Comments

0

linkyless commented on July 19, 2022, 10:02 p.m.

¿Cuándo sale la editorial para este ejercicio?

1

leocar commented on July 25, 2022, 5:28 p.m.

Ya esta el editorial de este ejercicio y de casi todos

0

linkyless commented on July 26, 2022, 12:29 a.m.

No veo la editorial de ningún otro ejercicio a excepción de "Locura de los monos". Si pudiera ser posible, revisen que esté en público la editorial. ¡Muchas gracias! <3

0

leocar commented on July 18, 2022, 6:28 p.m.

El caso de salida del ejemplo 3 es 0