Comiendo setas P14827


Statement
 

pdf   zip

thehtml

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] = 



c,si i = 1 y j = 1;
(d · T[i][j−1] + e) modp,si j > 1;
(d · T[i−1][n] + e) modp, si i > 1 y j = 1.

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 ‍
Public test cases
  • 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
    
  • Information
    Author
    Alex Alvarez
    Language
    Spanish
    Official solutions
    C++
    User solutions