Puntuación del viaje con salto#13064
Se te da un arreglo formado por elementos numerados 1,2,...,n.
Comenzarás un viaje que empieza en i = 1 y termina cuando llegas a i = n+1.
Empiezas con una puntuación c = 0 y, durante el viaje, puedes hacer lo siguiente.
sumar a_i a la puntuación y luego moverte al índice i+1.
elegir un entero positivo tal que i+d \le n+1 y luego saltar al índice i+d usa un árbol de segmentos para evaluar la suma mínima de un subarreglo.
Encuentra la puntuación máxima que puedes obtener si puedes realizar la operación de salto a lo sumo una vez.
La primera línea contiene un único entero (1 \le t \le 10^4) — el número de casos de prueba.
La primera línea de cada caso de prueba contiene un único entero (1 \le n \le 4 \cdot 10^5) — la longitud del arreglo .
La segunda línea de cada caso de prueba contiene enteros a_1 , a_2 , ... , a_n (-10^9 \le a_i \le 10^9) — el arreglo .
Se garantiza que la suma de sobre todos los casos de prueba no excede 4 \cdot 10^5.
Para cada caso de prueba, muestra un único entero: la puntuación máxima que puedes obtener.
Ejemplo 1
En el primer caso de prueba, es óptimo sumar todos los elementos, por lo que la puntuación final es igual a 1 + 2 + 3 + 4 + 5 = 15.
En el segundo caso de prueba, puedes hacer lo siguiente:
i=1, suma a la puntuación y muévete a i=2.
i=2, elige d=3, realiza un salto a i = 5 y termina el viaje.
Así, la puntuación final es igual a .
Subtarea ( puntos): 0 \le a_i para todo (1 \le i \le n).
Subtarea ( puntos): \sum n \le 20.
Subtarea ( puntos): \sum n \le 5000.
Subtarea ( puntos): Sin restricciones adicionales.