Un juego de cartas conocido como una prueba de intelecto se llama “Kang”. En este juego, cada carta tiene una puntuación que es un número entero positivo. Al comienzo, recibes $N$ cartas para tener en tu mano, y hay otras $M$ cartas colocadas boca arriba sobre la mesa ordenadas de izquierda a derecha. Puedes ver la puntuación de todas las cartas, tanto de las que recibiste en tu mano como de las que están sobre la mesa. Luego, puedes tomar cartas adicionales de la mesa durante $k$ rondas, tomando una carta a la vez en orden de izquierda a derecha. Después de cada ronda de tomar una carta, puedes descartar cartas de tu mano 1 vez, eliminando cualquier cantidad de cartas en tu mano que tengan la misma puntuación. Debes planificar tu estrategia de juego para que, después de tomar cartas de la mesa y descartar cartas de tu mano durante las $k$ rondas completas, las cartas restantes en tu mano tengan la menor suma de puntuaciones posible.
Considera el siguiente ejemplo.
Supongamos que al principio tienes cinco cartas con puntuaciones $6, 3, 9, 6, 3$ y las cartas colocadas sobre la mesa tienen puntuaciones ordenadas de izquierda a derecha $4, 6, 9, 6$.
Caso $k = 1$: Si solo puedes tomar 1 carta de la mesa, cuando tomas la primera carta, las puntuaciones de las cartas que tienes serán $6, 3, 9, 6, 3, 4$. Luego puedes elegir descartar cartas con la misma puntuación 1 vez; la mejor opción es elegir descartar 2 cartas con puntuación $6$, para que la suma de puntuaciones de las cartas restantes tenga el valor mínimo igual a $3 + 9 + 3 + 4 = 19$.
Caso $k = 2$: Si puedes tomar 2 cartas de la mesa, la mejor estrategia es: después de tomar la primera carta con puntuación $4$, eliges descartar una carta con puntuación $9$; las cartas restantes en tu mano tienen puntuaciones $6, 3, 6, 3, 4$. Luego, al tomar la 2.ª carta con puntuación $6$, podrás descartar 3 cartas con puntuación $6$, haciendo que las cartas restantes tengan la suma mínima de puntuaciones igual a $3 + 3 + 4 = 10$.
Caso $k = 3$: Si puedes tomar 3 cartas de la mesa, la mejor estrategia es: cuando tomas la primera carta, las puntuaciones de las cartas en tu mano serán $6, 3, 9, 6, 3, 4$. Luego eliges descartar cartas con la misma puntuación 1 vez; la mejor opción es descartar las 2 cartas con puntuación $3$, quedando en tu mano $6, 9, 6, 4$. A continuación, cuando tomas la 2.ª carta con puntuación $6$, podrás descartar 3 cartas con puntuación $6$, quedando en tu mano $9, 4$. Y cuando tomas por 3.ª vez una carta con puntuación $9$, podrás descartar las 2 cartas con puntuación $9$, haciendo que la carta restante tenga una puntuación total de $4$.
Caso $k = 4$: Si puedes tomar 4 cartas de la mesa, la mejor estrategia es: después de tomar la primera carta con puntuación $4$, elige descartar una carta con puntuación $4$, quedando en tu mano cartas con puntuaciones $6, 3, 9, 6, 3$. Luego, en la 2.ª toma, la carta tiene puntuación $6$; la mejor opción es descartar las 2 cartas con puntuación $3$, quedando en tu mano $6, 9, 6, 6$. En la 3.ª toma, la carta tiene puntuación $9$; elige descartar las 2 cartas con puntuación $9$. Y al tomar la última carta con puntuación $6$, podrás descartar 4 cartas con puntuación $6$. Este descarte hace que no queden cartas en tu mano, lo que significa que la suma de puntuaciones de las cartas es $0$.
Tu tarea (Your Task)
Encuentra la “suma mínima de las puntuaciones de las cartas restantes en la mano” después de terminar $k$ rondas, para $k = 1, 2, 3, \ldots, M$.
Este problema tiene un formato de programación diferente al formato habitual, el cual se utilizará en la competencia real. Por favor, consulta el final de este enunciado sobre cómo utilizarlo.
Detalles de implementación
Debes escribir la siguiente función:
std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)Con los siguientes parámetros:
- $A$ es un arreglo de longitud $N$ que indica los números de las cartas en la mano al inicio.
- $B$ es un arreglo de longitud $M$ que indica los números de las cartas colocadas sobre la mesa, ordenadas de izquierda a derecha.
- Dicha función debe devolver un arreglo $C$ de longitud $M$ que represente la menor suma posible de puntuaciones de las cartas en la mano tras $k$ rondas, para $k = 1, 2, 3, \ldots, M$.
Por ejemplo, si $A = [6, 3, 9, 6, 3]$ y $B = [4, 6, 9, 6]$, la función debe devolver el arreglo $[19, 10, 4, 0]$.
Restricciones
- $1 \le N, M \le 10^6$
- $1 \le A[i] \le 10^9$ para cada $i$ tal que $1 \le i \le N$
- $1 \le B[i] \le 10^9$ para cada $i$ tal que $1 \le i \le M$
Subtareas
| Grupo de casos de prueba | Puntuación máxima de este grupo | Condiciones |
|---|---|---|
| 1 | 5% | $N, M \le 5$ |
| 2 | 7% | $N \le 1\,000$ y $M = 1$ |
| 3 | 8% | $N, M \le 1\,000$, todas las cartas (tanto las de la mano como las mostradas en la mesa) tienen números distintos entre sí |
| 4 | 12% | $N, M \le 1\,000$, todas las cartas adicionales recibidas tienen el mismo valor |
| 5 | 16% | $N, M \le 1\,000$ |
| 6 | 28% | $N, M \le 100\,000$ |
| 7 | 24% | Sin condiciones adicionales |
Nota
Instrucciones de programación
Para este problema, la forma de escribir el programa y enviarlo al sistema evaluador (Grader) tiene un formato diferente al formato general de programación en el que el concursante debe escribir la parte de lectura de entrada y la parte de impresión de salida. En este problema, el concursante solo debe escribir la parte de cálculo necesaria dentro de la función especificada. Los distintos datos de entrada estarán disponibles a través de los parámetros de la función, y el resultado del cálculo también deberá devolverse a través de la función; el concursante no necesita escribir código para leer la entrada ni para mostrar la salida.
El concursante recibirá varios archivos como se detalla a continuación. El concursante deberá modificar únicamente el archivo indicado por el problema y enviar dicho archivo al sistema:
grader.cppes el archivo principal encargado de recibir la entrada y producir la salida.kang.cppes el archivo donde el concursante debe escribir los cálculos del programa y es el archivo que debe enviar al sistema (en el archivokang.cppno debe haber una funciónmain(), pero puede haber otras funciones).run_cpp.shes un archivo que el concursante puede invocar para ejecutar todo el programa.compile_cpp.shes un archivo que el concursante puede invocar para compilar el programa.
El concursante recibirá un archivo .zip que se puede descargar del sistema; al descomprimirlo (extract), contendrá los 4 archivos mencionados. El concursante debe usar un editor de texto o IDE para editar el archivo kang.cpp y compilar o ejecutar el programa invocando compile_cpp.sh o run_cpp.sh.
Cuando el concursante invoque el archivo run_cpp.sh para ejecutar el programa, este funcionará según lo especificado en el archivo grader.cpp, cuyo funcionamiento se explica en la sección “Descripción del archivo Grader”.