Se dan dos secuencias de enteros de longitud $n$, $B=[b_1,\ldots,b_n]$ y $C=[c_1,\ldots,c_n]$. Para una secuencia de enteros no negativos $D=[d_1,\ldots,d_n]$ de longitud $n$, sea $S(D)$ el conjunto de índices $i$ tales que $d_i=0$. Definimos $f(D)=\sum_{i\in S(D)}b_i$ y $g(D)=\prod_{i\in S(D)}c_i$. En particular, si $S(D)$ está vacío, $f(D)=0$ y $g(D)=1$.
小 L tiene una secuencia de enteros positivos $A=[a_1,\ldots,a_n]$ de longitud $n$. Puede modificarla de la siguiente manera:
- Elige dos índices adyacentes $i,j$ de $A$, es decir, $1\le i,j\le n$ y $|i-j|=1$. Si $a_i\le a_j$, sustituye $a_j$ por $a_j-a_i$ y, simultáneamente, sustituye $a_i$ por $0$.
小 L puede realizar cualquier número de operaciones, incluida ninguna. Entre todas las secuencias $D$ que pueden obtenerse de $A$ con estas operaciones, quiere encontrar el máximo de $f(D)$ y la suma de $g(D)$. Ayúdale a calcular ambos valores. Formalmente, sea $T(A)$ el conjunto de todas las secuencias que pueden obtenerse de $A$ mediante esas operaciones. Debes calcular $\max_{D\in T(A)}f(D)$ y $\sum_{D\in T(A)}g(D)$. Como la suma puede ser grande, solo tienes que dar su valor módulo $1\,000\,000\,007$.
Entrada
Los datos se leen del archivo sequence.in.
Este problema contiene varios casos de prueba.
La primera línea contiene dos enteros no negativos $c,t$, que indican respectivamente el número del punto de prueba y el número de casos. $c=0$ indica que se trata de un ejemplo.
Los casos se dan a continuación, uno tras otro. Para cada caso:
La primera línea contiene un entero positivo $n$, la longitud de las secuencias.
La segunda línea contiene $n$ enteros positivos $a_1,\ldots,a_n$, que representan $A$.
La tercera línea contiene $n$ enteros $b_1,\ldots,b_n$, que representan $B$.
La cuarta línea contiene $n$ enteros positivos $c_1,\ldots,c_n$, que representan $C$.
Salida
Escribe la salida en el archivo sequence.out.
Para cada caso de prueba, escribe una línea con dos enteros: $\max_{D\in T(A)}f(D)$ y el valor de $\sum_{D\in T(A)}g(D)$ módulo $1\,000\,000\,007$, respectivamente. Ten en cuenta que no debes reducir $\max_{D\in T(A)}f(D)$ módulo $1\,000\,000\,007$.
Este problema contiene dos apartados. Resolver correctamente cualquiera de ellos permite obtener puntuación parcial. Consulta las reglas concretas en «Subtareas».
Ejemplos
Entrada 1
0 3 3 5 6 6 3 6 9 1 2 3 6 1 1 4 5 1 4 -1 1 -1 1 -2 2 1 1 1 1 1 1 8 4 2 4 2 2 2 4 4 -2 4 9 -3 4 8 7 8 1 1 1 1 1 1 1 1
Salida 1
15 10 1 18 37 48
Nota
Este ejemplo contiene tres casos de prueba.
En el primer caso se pueden obtener las 4 secuencias siguientes:
- $D=[5,6,6]$, $f(D)=0$, $g(D)=1$.
- $D=[0,1,6]$, $f(D)=3$, $g(D)=1$.
- $D=[5,0,0]$, $f(D)=6+9=15$, $g(D)=2\times3=6$.
- $D=[0,0,5]$, $f(D)=3+6=9$, $g(D)=1\times2=2$.
Por tanto, $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$ y $\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
Ejemplo 2
Consulta sequence/sequence2.in y sequence/sequence2.ans en el directorio del concursante.
Este ejemplo cumple las restricciones de los puntos de prueba $3,4$.
Ejemplo 3
Consulta sequence/sequence3.in y sequence/sequence3.ans en el directorio del concursante.
Este ejemplo cumple las restricciones de los puntos de prueba $5,6$.
Ejemplo 4
Consulta sequence/sequence4.in y sequence/sequence4.ans en el directorio del concursante.
Este ejemplo cumple las restricciones del punto de prueba $7$.
Ejemplo 5
Consulta sequence/sequence5.in y sequence/sequence5.ans en el directorio del concursante.
Este ejemplo cumple las restricciones de los puntos de prueba $11,12$.
Ejemplo 6
Consulta sequence/sequence6.in y sequence/sequence6.ans en el directorio del concursante.
Este ejemplo cumple las restricciones de los puntos de prueba $16\sim18$.
Restricciones
Sea $N$ la suma de los valores de $n$ de todos los casos de un mismo punto de prueba. Para todos los datos, se garantiza lo siguiente:
- $1\le t\le20$.
- $1\le n\le5000$, $N\le4\times10^4$.
- Para todo $1\le i\le n$, $1\le A_i\le10^9$.
- Para todo $1\le i\le n$, $-10^9\le B_i\le10^9$.
- Para todo $1\le i\le n$, $1\le C_i\le10^9$.
| Números de los puntos de prueba | $n\le$ | $N\le$ | Propiedad especial |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | Ninguna |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | Ninguna |
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | Ninguna |
| $13$ | $3500$ | $3\times10^4$ | A |
| $14,15$ | $3500$ | $3\times10^4$ | B |
| $16\sim18$ | $3500$ | $3\times10^4$ | Ninguna |
| $19,20$ | $5000$ | $4\times10^4$ | Ninguna |
Propiedad especial A: se garantiza que $A_1=A_2=\cdots=A_n=1$.
Propiedad especial B: para todo $1\le i\le n$, cada $A_i$ se genera de manera independiente y uniforme en $[1,10^9]$.
Subtareas
Para cada punto de prueba:
- Responder correctamente $\max_{D\in T(A)}f(D)$ en todos sus casos proporciona el 40 % de sus puntos.
- Responder correctamente el valor de $\sum_{D\in T(A)}g(D)$ módulo $1\,000\,000\,007$ en todos sus casos proporciona el 60 % de sus puntos.
Atención: aunque solo respondas a uno de los apartados, debes escribir los dos enteros requeridos por el formato de salida, correspondientes a las respuestas de los dos apartados.