Erästä älykkyystestiksi kutsuttua korttipeliä nimitetään ”Kang”-peliksi. Tässä pelissä jokaisella kortilla on pistemäärä, joka on positiivinen kokonaisluku. Aluksi saat käteesi $N$ korttia, ja pöydällä on lisäksi $M$ korttia kuvapuoli ylöspäin järjestettynä vasemmalta oikealle, jolloin näet kaikkien korttien pistemäärät — sekä käteen saamiesi että pöydällä olevien. Tämän jälkeen voit nostaa pöydältä lisää kortteja $k$ kierroksen ajan siten, että kortteja on nostettava yksi kerrallaan järjestyksessä vasemmalta oikealle. Kunkin kierroksen kortin nostamisen jälkeen voit poistaa kädestäsi kortteja 1 kerran — kuinka monta tahansa kädessäsi olevaa korttia, joilla on sama pistemäärä. Sinun tulee suunnitella pelisi siten, että kun olet nostanut kortteja pöydältä ja poistanut kortteja kädestäsi täydet $k$ kierrosta, käteen jääneiden korttien yhteispistemäärä on mahdollisimman pieni.

Tarkastellaan seuraavaa esimerkkiä:

Jos sinulla on alussa viisi korttia, joiden pistemäärät ovat $6, 3, 9, 6, 3$, ja pöydällä olevien korttien pistemäärät vasemmalta oikealle ovat $4, 6, 9, 6$:

Tapaus $k = 1$: Jos voit nostaa pöydältä vain 1 kortin, ensimmäisen kortin nostamisen jälkeen korttiesi pistemäärät ovat $6, 3, 9, 6, 3, 4$. Tämän jälkeen voit valita ja poistaa saman pistemäärän kortteja 1 kerran. Paras tapa on poistaa 2 korttia, joiden pistemäärä on $6$, jotta jäljelle jäävien korttien yhteispistemäärä on mahdollisimman pieni eli $3 + 9 + 3 + 4 = 19$.

Tapaus $k = 2$: Jos voit nostaa pöydältä 2 korttia, paras tapa on: nostettuasi ensimmäisen kortin, jonka pistemäärä on $4$, valitset poistettavaksi yhden kortin, jonka pistemäärä on $9$. Käteen jäävien korttien pistemäärät ovat $6, 3, 6, 3, 4$. Kun sitten nostat 2. kortin, jonka pistemäärä on $6$, voit poistaa 3 korttia, joiden pistemäärä on $6$, jolloin jäljelle jäävien korttien yhteispistemäärä on mahdollisimman pieni eli $3 + 3 + 4 = 10$.

Tapaus $k = 3$: Jos voit nostaa pöydältä 3 korttia, paras tapa on: kun nostat ensimmäisen kortin, kädessä olevien korttien pistemäärät ovat $6, 3, 9, 6, 3, 4$. Tämän jälkeen voit poistaa saman pistemäärän kortteja 1 kerran, ja paras tapa on poistaa molemmat (2) korttia, joiden pistemäärä on $3$, jolloin käteen jäävät kortit $6, 9, 6, 4$. Kun sitten nostat 2. kortin, jonka pistemäärä on $6$, voit poistaa 3 korttia, joiden pistemäärä on $6$, jolloin käteen jäävät kortit $9, 4$. Ja kun nostat 3. kerralla kortin, jonka pistemäärä on $9$, voit poistaa molemmat (2) korttia, joiden pistemäärä on $9$, jolloin jäljelle jäävien korttien yhteispistemääräksi tulee $4$.

Tapaus $k = 4$: Jos voit nostaa pöydältä 4 korttia, paras tapa on: nostettuasi ensimmäisen kortin, jonka pistemäärä on $4$, valitse poistettavaksi yksi kortti, jonka pistemäärä on $4$, jolloin käteen jäävät kortit pistemääriltään $6, 3, 9, 6, 3$. Sitten 2. nostolla kortin pistemäärä on $6$; paras tapa on poistaa molemmat (2) korttia, joiden pistemäärä on $3$, jolloin käteen jäävät kortit $6, 9, 6, 6$. 3. nostolla kortin pistemäärä on $9$; valitse poistettavaksi molemmat (2) korttia, joiden pistemäärä on $9$. Ja nostaessasi viimeisen kortin, jonka pistemäärä on $6$, voit poistaa 4 korttia, joiden pistemäärä on $6$. Tämän poiston seurauksena käteen ei jää yhtään korttia, mikä tarkoittaa, että korttien yhteispistemäärä on $0$.

Tehtäväsi (Your Task)

Etsi ”käteen jääneiden korttien pienin mahdollinen yhteispistemäärä” $k$ kierroksen päätyttyä, kun $k = 1, 2, 3, \ldots, M$.

Tässä tehtävässä ohjelmointimuoto poikkeaa tavallisesta muodosta, ja sitä käytetään varsinaisessa kilpailussa. Katso tehtävän lopusta ohjeet sen käyttämiseen.

Toteutuksen yksityiskohdat

Sinun tulee kirjoittaa seuraava funktio:

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

jolla on seuraavat parametrit:

• $A$ on pituuden $N$ taulukko, joka ilmaisee kädessä alussa olevien korttien numerot.
• $B$ on pituuden $M$ taulukko, joka ilmaisee pöydällä olevien korttien numerot järjestyksessä vasemmalta oikealle.
• Kyseisen funktion tulee palauttaa pituuden $M$ taulukko $C$, joka edustaa kädessä olevien korttien pienintä mahdollista yhteispistemäärää $k$ kierroksen jälkeen, kun $k = 1, 2, 3, \ldots, M$.

Esimerkiksi jos $A = [6, 3, 9, 6, 3]$ ja $B = [4, 6, 9, 6]$, funktion tulee palauttaa taulukko $[19, 10, 4, 0]$.

Rajoitukset

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ jokaisella $i$, jolla $1 \le i \le N$
• $1 \le B[i] \le 10^9$ jokaisella $i$, jolla $1 \le i \le M$

Osatehtävät

Huomautus

Ohjelmointiohjeet

Tässä tehtävässä tapa kirjoittaa ohjelma ja lähettää se tarkistusjärjestelmään (Grader) poikkeaa yleisestä ohjelmointimuodosta, jossa kilpailijan on kirjoitettava syötteen lukeva osa ja tulostava osa. Tässä tehtävässä kilpailijan tarvitsee kirjoittaa vain tarvittava laskentaosa annettuun funktioon. Syötetiedot ovat käytettävissä funktion parametrien kautta, ja laskennan tulokset on myös palautettava funktion kautta, joten kilpailijan ei tarvitse kirjoittaa syötteen lukemista eikä tulostamista.

Kilpailija saa käyttöönsä seuraavat tiedostot; kilpailijan tulee muokata vain yhtä tehtävän määräämää tiedostoa ja lähettää kyseinen tiedosto järjestelmään:

• grader.cpp on päätiedosto, joka huolehtii syötteen lukemisesta ja tulostamisesta.
• kang.cpp on tiedosto, johon kilpailijan tulee kirjoittaa varsinainen laskentaohjelma ja jonka kilpailija lähettää järjestelmään (tiedostossa kang.cpp ei saa olla main()-funktiota, mutta muita funktioita saa olla).
• run_cpp.sh on tiedosto, jota kilpailija voi kutsua koko ohjelman suorittamiseksi.
• compile_cpp.sh on tiedosto, jota kilpailija voi kutsua ohjelman kääntämiseksi.

Kilpailija saa järjestelmästä ladattavan .zip-tiedoston, joka purettaessa (extract) sisältää kaikki 4 tiedostoa. Kilpailijan tulisi käyttää tekstieditoria (text editor) tai IDE-ympäristöä kang.cpp-tiedoston muokkaamiseen sekä kääntää tai suorittaa ohjelma kutsumalla tiedostoa compile_cpp.sh tai run_cpp.sh.

Kun kilpailija kutsuu run_cpp.sh-tiedostoa suorittaakseen ohjelman, ohjelma toimii grader.cpp-tiedostossa määritellyllä tavalla, ja osio ”Tarkistustiedoston kuvaus” selittää kyseisen tiedoston toiminnan.