Et kortspill som omtales som en intelligenstest, heter «Kang». I dette spillet har hvert kort en poengverdi som er et positivt heltall. I starten får du utdelt $N$ kort til å ha på hånden, og det ligger ytterligere $M$ kort med forsiden opp på bordet, ordnet fra venstre til høyre, slik at du ser poengverdien til alle kortene — både de du har fått på hånden og de som ligger på bordet. Deretter kan du trekke flere kort fra bordet i $k$ runder, der du må trekke ett kort om gangen i rekkefølge fra venstre til høyre. Etter at du har trukket et kort i hver runde, kan du kaste kort fra hånden 1 gang — så mange kort fra hånden du vil som har samme poengverdi. Du må legge en spilleplan slik at etter at du har trukket kort fra bordet og kastet kort fra hånden i $k$ runder, har kortene som er igjen på hånden minst mulig samlet poengsum.

Betrakt følgende eksempel:

Hvis du i starten har fem kort med poengverdiene $6, 3, 9, 6, 3$, og kortene som ligger på bordet fra venstre til høyre har poengverdiene $4, 6, 9, 6$:

Tilfellet $k = 1$: Hvis du bare kan trekke 1 kort fra bordet, vil poengverdiene til kortene du har etter å ha trukket det første kortet være $6, 3, 9, 6, 3, 4$. Deretter kan du velge å kaste kort med samme poengverdi 1 gang. Den beste måten er å velge å kaste 2 kort med poengverdi lik $6$, slik at poengsummen til de gjenværende kortene blir minst mulig, lik $3 + 9 + 3 + 4 = 19$.

Tilfellet $k = 2$: Hvis du kan trekke 2 kort fra bordet, er den beste måten: etter å ha trukket det første kortet med poengverdi lik $4$, velger du å kaste ett kort med poengverdi lik $9$. De gjenværende kortene på hånden har poengverdiene $6, 3, 6, 3, 4$. Når du deretter trekker det 2. kortet med poengverdi lik $6$, kan du kaste 3 kort med poengverdi lik $6$, noe som gjør at de gjenværende kortene får minst mulig poengsum lik $3 + 3 + 4 = 10$.

Tilfellet $k = 3$: Hvis du kan trekke 3 kort fra bordet, er den beste måten: når du trekker det første kortet, vil poengverdiene til kortene på hånden være $6, 3, 9, 6, 3, 4$. Deretter kan du velge kort med samme poengverdi å kaste 1 gang, og den beste måten er å kaste begge de 2 kortene med poengverdi lik $3$, slik at kortene $6, 9, 6, 4$ blir igjen på hånden. Når du deretter trekker det 2. kortet med poengverdi lik $6$, kan du kaste 3 kort med poengverdi lik $6$, slik at du har kortene $9, 4$ på hånden. Og når du for 3. gang trekker et kort med poengverdi lik $9$, kan du kaste begge de 2 kortene med poengverdi lik $9$, slik at de gjenværende kortene får en samlet poengsum på $4$.

Tilfellet $k = 4$: Hvis du kan trekke 4 kort fra bordet, er den beste måten: etter å ha trukket det første kortet med poengverdi lik $4$, velg å kaste ett kort med poengverdi lik $4$, slik at det blir igjen kort på hånden med poengverdiene $6, 3, 9, 6, 3$. Ved 2. trekk har kortet poengverdi lik $6$; den beste måten er å kaste begge de 2 kortene med poengverdi lik $3$, slik at kortene på hånden blir $6, 9, 6, 6$. Ved 3. trekk har kortet poengverdi lik $9$; velg å kaste begge de 2 kortene med poengverdi lik $9$. Og når du trekker det siste kortet med poengverdi lik $6$, kan du kaste 4 kort med poengverdi lik $6$. Dette kastet fører til at det ikke er noen kort igjen på hånden, hvilket betyr at poengsummen til kortene er $0$.

Din oppgave (Your Task)

Finn «den minste poengsummen for kortene som er igjen på hånden» etter fullførte $k$ runder når $k = 1, 2, 3, \ldots, M$.

Denne oppgaven har et annet programmeringsformat enn det vanlige formatet, og dette formatet vil bli brukt i selve konkurransen. Se slutten av denne oppgaven for informasjon om hvordan det brukes.

Implementasjonsdetaljer

Du må skrive følgende funksjon:

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

med følgende parametere:

• $A$ er en tabell (array) av lengde $N$ som angir numrene på kortene på hånden i starten.
• $B$ er en tabell (array) av lengde $M$ som angir numrene på kortene som ligger på bordet, ordnet fra venstre til høyre.
• Funksjonen må returnere en tabell $C$ av lengde $M$ som representerer den minste mulige poengsummen for kortene på hånden etter $k$ runder når $k = 1, 2, 3, \ldots, M$.

For eksempel, hvis $A = [6, 3, 9, 6, 3]$ og $B = [4, 6, 9, 6]$, må funksjonen returnere tabellen $[19, 10, 4, 0]$.

Begrensninger

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ for hver $i$ der $1 \le i \le N$
• $1 \le B[i] \le 10^9$ for hver $i$ der $1 \le i \le M$

Deloppgaver

Merk

Programmeringsinstruksjoner

For denne oppgaven er måten å skrive programmet og sende det inn til bedømmingssystemet (Grader) på ulik det vanlige programmeringsformatet der deltakeren må skrive delen som leser innndata og delen som skriver ut utdata. I denne oppgaven skal deltakeren kun skrive den nødvendige beregningsdelen inne i den oppgitte funksjonen. De ulike inndataene vil være tilgjengelige gjennom funksjonens parametere, og beregningsresultatene må også returneres via funksjonen, uten at deltakeren trenger å skrive kode for innlesing av inndata eller utskrift av utdata.

Deltakeren vil motta flere filer som følger; deltakeren må kun endre én enkelt fil slik oppgaven spesifiserer, og sende inn denne filen til systemet:

• grader.cpp er hovedfilen som har som oppgave å lese inndata og skrive utdata.
• kang.cpp er filen der deltakeren må skrive de ulike beregningene i programmet, og er filen som deltakeren sender inn til systemet (i filen kang.cpp er det ikke tillatt å ha funksjonen main(), men andre funksjoner er tillatt).
• run_cpp.sh er filen deltakeren kan kalle for å kjøre hele programmet.
• compile_cpp.sh er filen deltakeren kan kalle for å kompilere programmet.

Deltakeren vil motta en .zip-fil som kan lastes ned fra systemet; når denne filen pakkes ut (extract), vil alle de 4 filene ligge der. Deltakeren bør bruke en teksteditor (text editor) eller et IDE for å redigere filen kang.cpp, og kompilere eller kjøre programmet ved å kalle compile_cpp.sh eller run_cpp.sh.

Når deltakeren kaller filen run_cpp.sh for å kjøre programmet, vil programmet fungere slik det er angitt i filen grader.cpp, der avsnittet «Beskrivelse av grader-filen» forklarer hvordan denne filen fungerer.