Problem F
Virkne
Languages
da
de
en
et
fi
lt
lv
pl
uk
Virkne no naturāliem skaitļiem $(x_1, \ldots , x_ m)$ ir laba, ja $x_1 = 1$ un katram $1 < j \leq m$ izpildās vai nu $x_ j = x_{j-1}+1$ vai $x_ j = x_ k \cdot x_ l$ kādām $k$ un $l$ vērtībām ar $0 < k \leq l < j$. Piemēram, virknes $(1,1)$ un $(1,2)$ abas ir labas, bet virkne $(1,3)$ nav laba. Dotiem $n$ veseliem skaitļiem $w_1, \ldots , w_ n$ definēsim svaru no kādas veselas skaitļu virknes $(x_1, \ldots , x_ m)$, kas apmierina $1 \leq x_ j \leq n$ visiem $1 \leq j \leq m$, kā
\[ w_{x_1} + \cdots + w_{x_ m}. \]Piemēram, dotiem svariem $w_1 = 10$, $w_2 = 42$, $w_3 = 1$, virknes $(1,1)$ svars ir $20$ un virknes $(1,3)$ svars ir $11$. Katram $1\leq v\leq n$ definēsim $s_ v$ kā mazāko iespējamo svaru kādai labai skaitļu virknei, kas satur skaitli $v$.
Jūsu uzdevums ir noteikt vērtības $s_1,\ldots ,s_ n$.
Ievaddati
Pirmā ievada rinda satur veselo skaitli $n$, svaru skaitu. Nākamās $n$ rindas satur svarus, veselus skaitļus $w_1, \ldots , w_ n$.
Izvaddati
Izvadiet $n$ rindas, kas satur $s_1$, $\ldots $, $s_ n$ šādā secībā.
Ierobežojumi un vērtēšana
Vienmēr izpildās ierobežojumi $1\leq n \leq 30\, 000$ un $1\leq w_ i \leq 10^6$ visiem $1\leq i \leq n$.
Jūsu risinājums tiks pārbaudīts uz vairākām testu grupām. Katra grupa ir vērta noteiktu punktu skaitu. Katra testu grupa satur vairākus testus. Lai saņemtu punktus par testu grupu, ir jāatrisina visi testi testu grupā. Jūsu gala rezultāts būs lielākais punktu skaits, kas iegūts ar vienu risinājuma iesniegumu.
|
Grupa |
Punkti |
Ierobežojumi |
|
$1$ |
$11$ |
$n\leq 10$ |
|
$2$ |
$10$ |
$n\leq 300$, $w_1=\cdots =w_ n = 1$ |
|
$3$ |
$10$ |
$n\leq 300$, $w_1=\cdots =w_ n$ |
|
$4$ |
$9$ |
$n\leq 1400$, $w_1=\cdots =w_ n = 1$ |
|
$5$ |
$45$ |
$n\leq 5000$ |
|
$6$ |
$15$ |
Bez papildu ierobežojumiem |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
