Problem C
Ding Dong Ditch
Languages
en
sv
Raunak och hans vänner vill dra ett skämt på sina grannar genom att utföra det klassiska "Ding Dong Ditch". De vill i tur och ordning plinga på ringklockan på ett antal av sina grannar, och sedan springa därifrån utan att grannarna ser dem. Men vissa grannar är väldigt farliga, då grannarna kan bli agra och kan även bitas!
På deras gata finns det $N$ grannar. För varje granne $i$ har grannen ett värde på hur arg grannen blir efter att ha blivit plingad på, $A_ i$. Raunak har $Q$ vänner, inklusive han själv. För varje vän $j$ har vännen en egen ambitionsnivå $B_ j$ som står för antalet hus den kan plinga på innan vännen fegar ut.
För varje vän som plingar på vill den välja $B_ j$ olika hus, och minimera summan av arghetsvärdena $A_ i$ av alla dessa hus. Hjälp Raunak att lista ut vad den minsta möjliga summan av arghetsvärdet som varje vän kan uppnå!
Notera att olika vänner kan plinga på samma hus.
Indata
Första raden består av två positiva heltal $1 \leqslant N \leqslant 2 \cdot 10^5$ respektive $1 \leqslant Q \leqslant 10^5$ som motsvarar antalet hus som finns i grannskapet respektive antalet vänner som Raunak har. Raden efter består av $N$ distinkta positiva heltal separerade med mellanslag, där varje heltal $1 \leqslant A_ i \leqslant 10^9$ är arghetsvärdet på vardera. Sista raden består av $Q$ positiva heltal separerade med mellanslag, där varje heltal $1 \leqslant B_ j \leqslant N$ står för antalet hus vardera vän ska plinga på vid.
Utdata
Skriv ut $Q$ rader, där varje rad består ett heltal - Det minsta summan av arghetsvärdena av husen som vännen $j$ plingat på.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$10$ |
$Q=1, N \leqslant 10$ |
|
$2$ |
$25$ |
$Q\leqslant 10^3, N \leqslant 100$ |
|
$3$ |
$10$ |
Alla $B_ j$ är antingen $1$ eller $N$. |
|
$4$ |
$20$ |
$Q\leqslant 10^3, N \leqslant 10^4$ |
|
$5$ |
$35$ |
Inga ytterligare begränsningar |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 3 2 1 4 3 1 |
6 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 1 12 2 14 6 9 3 |
17 |
