Tres-Veltör y su Batallón
El joven vikingo Tres-Veltör es ahora el nuevo comandante de el batallón de infantería del Valhalla. Sus guerreros hoy están practicando unos ejercicios tácticos de modo preventivo para el Ragnarök. Sus guerreros están ubicados en una línea recta, cada uno ocupando la posición y con una fuerza . Como todo no es coser y cantar Tres-Veltör se dio cuenta que sus guerreros estaban demasiado cerca entre ellos y si manda al guerrero a la batalla no puede mandar a sus adyacentes (note que el primero y el último solo tienen un adyacente) ya que se harían daño entre ellos. Tres-Veltör puede mandar cualquier subconjunto de guerreros siempre que cumpla con estos requisitos incluso si este está vacío.
El batallón realizará ejercicios tácticos, antes de cada ejercicio un guerrero de Tres-Veltör tomará una poción mágica que cambiará su fuerza actual hasta que este tome otra poción. Su tarea es decirle a Tres-Veltör antes de cada ejercicio táctico cuál es la mayor fuerza que puede lograr su batallón.
Entrada
La primera línea contiene los enteros y (), el número de guerreros de Tres-Veltör y la cantidad de ejercicios tácticos.
La segunda línea contiene enteros separados por espacio donde el -ésimo entero representa a (), la fuerza del -ésimo guerrero.
Las siguientes líneas contienen dos enteros () y () que significan que el guerrero con índice ahora tiene una fuerza igual a (i. e. ).
Salida
líneas donde la -ésima línea posee un entero que representa la mayor fuerza posible del batallón luego de que el guerrero con indice tome su poción.
Subtareas
- Subtarea 1 (5 puntos): .
- Subtarea 2 (12 puntos): .
- Subtarea 3 (13 puntos): .
- Subtarea 4 (20 puntos): es una potencia de .
- Subtarea 5 (40 puntos): Sin restricciones adicionales.
Ejemplo #1 de Entrada
5 9
0 0 0 0 1
1 2
2 5
3 10
4 9
2 -1
3 -3
1 -4
4 -2
5 -1
Ejemplo #1 de Salida
3
6
13
14
13
11
9
1
0
Ejemplo #2 de Entrada
5 3
1
2
3
4
5
5 2
2 7
1 10
Ejemplo #2 de Salida
6
11
15
Comments
Bro he intentado escribirte pero no te llega ningun mensaje.Mi alias es hohemhein20 . Intenta tu a ver si llega
Como puedo resolver este ejercicio?
Si tienes telegram puedes escribirme y puedo explicarte por privado, mi alias es @albertolg101