Comiendo setas P14827
Alicia y Benito tienen n setas en común, y se las quieren comer todas en orden: primero la seta 1, luego la 2, …Cada seta será comida enteramente por Alicia o por Benito. Se sabe que comer la seta i-ésima provocaría satisfacción Ai a Alicia, y satisfacción Bi a Benito. Son buenos amigos, por lo que han decidido maximizar la suma de las satisfacciones de ambos, sin importar cuántas setas comerá cada uno.
Sin embargo, existe un problema. Como las setas tienen un gusto fuerte, si cualquiera de ellos se come la seta j cuando la última seta que se había comido era la i, se deberá restar un cierto valor T[i][j] a la satisfacción total obtenida.
¿Podéis calcular la máxima satisfacción total posible, si se decide quién se come cada seta de forma óptima?
Entrada
La entrada consiste en diversos casos, y sólo contiene números enteros no negativos. Cada caso empieza con cinco números n, c, d, e y p. Siguen A1, ..., An y B1, ..., Bn. Asumid n ≥ 1, que c, d y e son menores que p, p ≤ 1000, y que todas las Ai y las Bi están entre 0 y 1000.
Los valores c, d, e y p se dan para definir la matriz T[1..n][1..n] de forma implícita, de la forma siguiente:
| T[i][j] = | ⎧ ⎪ ⎨ ⎪ ⎩ |
|
Esta definición de la matriz T no tiene ningún truco, simplemente sirve para que la entrada sea relativamente pequeña y rápida de leer.
Salida
Para cada caso, escribid la máxima satisfacción posible.
Puntuación
- test-1: Casos con n ≤ 1000 y donde T sólo tiene ceros, como el Ejemplo 1. 25 Puntos
- test-2: Casos con n ≤ 10, como el Ejemplo 2. 25 Puntos
- test-3: Casos con n ≤ 100. 25 Puntos
- test-4: Casos con n ≤ 1000. 25 Puntos
Input
8 0 87 0 907 85 184 954 399 786 592 614 345 464 886 516 368 424 620 51 15 1 0 2 0 7 42 23
Output
5068 42
Input
10 98 69 139 149 497 710 164 512 602 316 669 9 569 541 242 112 420 445 426 221 147 81 922 813 2 460 275 366 487 933 878 87 105 3 100 17 403 997 1 2 3 4 5 6
Output
5093 1565 -97
- Author
- Alex Alvarez
- Language
- Spanish
- Official solutions
- C++
- User solutions