Un jeu de cartes réputé comme étant une épreuve d'intelligence s'appelle « Kang ». Dans ce jeu, chaque carte possède un score qui est un entier strictement positif. Au début, vous recevez $N$ cartes à garder en main, et $M$ autres cartes sont posées faces visibles sur la table, alignées de gauche à droite. Vous voyez le score de toutes les cartes, aussi bien celles reçues en main que celles posées sur la table. Ensuite, vous pouvez piocher des cartes supplémentaires sur la table pendant $k$ tours, en les prenant une par une de gauche à droite. Après chaque tour de pioche, vous pouvez effectuer 1 défausse depuis votre main, en jetant autant de cartes de votre main que vous le souhaitez tant qu'elles ont toutes le même score. Vous devez planifier votre jeu de sorte qu'après avoir pioché sur la table et défaussé de votre main pendant les $k$ tours, la somme des scores des cartes restantes dans votre main soit minimale.

Considérons l'exemple suivant.

Supposons qu'au départ vous ayez cinq cartes en main avec les scores $6, 3, 9, 6, 3$ et que les cartes posées sur la table aient, de gauche à droite, les scores $4, 6, 9, 6$.

Cas $k = 1$ : Si vous ne pouvez piocher qu'une seule carte sur la table, lorsque vous prenez la première carte, les scores des cartes que vous avez deviennent $6, 3, 9, 6, 3, 4$. Vous pouvez alors choisir de défausser 1 fois des cartes ayant le même score. Le meilleur choix consiste à défausser 2 cartes de score $6$, afin que la somme des scores des cartes restantes soit minimale et égale à $3 + 9 + 3 + 4 = 19$.

Cas $k = 2$ : Si vous pouvez piocher 2 cartes sur la table, la meilleure stratégie est la suivante : après avoir pioché la première carte de score $4$, vous choisissez de défausser une carte de score $9$. Les cartes restantes dans votre main ont pour scores $6, 3, 6, 3, 4$. Ensuite, lorsque vous piochez la 2-ème carte de score $6$, vous pouvez défausser 3 cartes de score $6$, ce qui donne aux cartes restantes une somme minimale de scores égale à $3 + 3 + 4 = 10$.

Cas $k = 3$ : Si vous pouvez piocher 3 cartes sur la table, la meilleure stratégie est la suivante : lorsque vous piochez la première carte, les scores des cartes en main deviennent $6, 3, 9, 6, 3, 4$. Vous choisissez ensuite de défausser 1 fois des cartes de même score ; le meilleur choix est de défausser les 2 cartes de score $3$, laissant en main $6, 9, 6, 4$. Ensuite, lorsque vous piochez la 2-ème carte de score $6$, vous pouvez défausser 3 cartes de score $6$, laissant en main $9, 4$. Et lorsque vous piochez pour la 3-ème fois une carte de score $9$, vous pouvez défausser les 2 cartes de score $9$, ce qui laisse une somme des scores des cartes restantes égale à $4$.

Cas $k = 4$ : Si vous pouvez piocher 4 cartes sur la table, la meilleure stratégie est la suivante : après avoir pioché la première carte de score $4$, choisissez de défausser une carte de score $4$, laissant en main les cartes de scores $6, 3, 9, 6, 3$. Puis, lors de la 2-ème pioche, la carte a un score de $6$ ; le meilleur choix est de défausser les 2 cartes de score $3$, laissant en main $6, 9, 6, 6$. Lors de la 3-ème pioche, la carte a un score de $9$ ; choisissez de défausser les 2 cartes de score $9$. Enfin, en piochant la dernière carte de score $6$, vous pouvez défausser 4 cartes de score $6$. Cette défausse a pour effet de ne laisser aucune carte en main, ce qui signifie que la somme des scores des cartes est $0$.

Votre tâche (Your Task)

Trouver la « somme minimale des scores des cartes restantes en main » à la fin de $k$ tours, pour $k = 1, 2, 3, \ldots, M$.

Ce problème utilise un format de programmation différent du format habituel, tel qu'il est employé lors de la compétition réelle. Veuillez consulter la fin de cet énoncé pour les instructions d'utilisation.

Détails d'implémentation

Vous devez écrire la fonction suivante :

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

Avec les paramètres suivants :

• $A$ est un tableau de longueur $N$ indiquant les numéros des cartes en main au départ.
• $B$ est un tableau de longueur $M$ indiquant les numéros des cartes posées sur la table, ordonnées de gauche à droite.
• Cette fonction doit renvoyer un tableau $C$ de longueur $M$ représentant la somme minimale possible des scores des cartes en main après $k$ tours, pour $k = 1, 2, 3, \ldots, M$.

Par exemple, si $A = [6, 3, 9, 6, 3]$ et $B = [4, 6, 9, 6]$, la fonction doit renvoyer le tableau $[19, 10, 4, 0]$.

Contraintes

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ pour chaque $i$ tel que $1 \le i \le N$
• $1 \le B[i] \le 10^9$ pour chaque $i$ tel que $1 \le i \le M$

Sous-tâches

Remarque

Instructions de programmation

Pour ce problème, la méthode d'écriture et de soumission du programme au système d'évaluation (Grader) diffère du format habituel où les candidats doivent écrire le code de lecture de l'entrée et d'affichage de la sortie. Dans ce problème, les candidats doivent uniquement écrire la partie de calcul nécessaire à l'intérieur de la fonction imposée. Les différentes données d'entrée sont accessibles via les paramètres de la fonction, et le résultat du calcul doit également être renvoyé par cette fonction, sans que les candidats aient à coder la lecture de l'entrée ni l'affichage de la sortie.

Les candidats recevront plusieurs fichiers comme suit. Les candidats doivent modifier uniquement le fichier spécifié par l'énoncé et soumettre ce fichier au système :

• grader.cpp est le fichier principal chargé de lire les données d'entrée et d'écrire les données de sortie.
• kang.cpp est le fichier dans lequel les candidats doivent écrire leurs calculs et qu'ils doivent soumettre au système (le fichier kang.cpp ne doit pas contenir de fonction main(), mais d'autres fonctions sont autorisées).
• run_cpp.sh est un fichier que les candidats peuvent appeler pour exécuter l'ensemble du programme.
• compile_cpp.sh est un fichier que les candidats peuvent appeler pour compiler le programme.

Les candidats recevront une archive .zip téléchargeable depuis le système ; une fois extraite (extract), elle contient ces 4 fichiers. Les candidats doivent utiliser un éditeur de texte ou un IDE pour modifier kang.cpp, et compiler ou exécuter le programme en appelant compile_cpp.sh ou run_cpp.sh.

Lorsque les candidats appellent run_cpp.sh pour exécuter le programme, celui-ci fonctionne comme spécifié dans le fichier grader.cpp, dont le fonctionnement est détaillé dans la section « Description du fichier Grader ».