Problem C
Sequence
A sequence of positive integers $(x_1,\ldots ,x_ m)$ is good if $x_1 = 1$ and for each $1 < j \leq m$ we have either $x_ j=x_{j-1}+1$ or $x_ j=x_ k\cdot x_ l$ for some $k$ and $l$ with $0< k\leq l< j$. For instance, the sequences $(1,1)$ and $(1,2)$ are both good, but the sequence $(1,3)$ is not good. For $n$ given integers $w_1,\ldots ,w_ n$ define the weight of an integer sequence $(x_1,\ldots ,x_ m)$ satisfying $1\leq x_ j \leq n$ for each $1\leq j\leq m$ as
\[ w_{x_1} +\cdots +w_{x_ m}\, . \]For instance, given the weights $w_1=10, w_2=42,w_3= 1$, the weight of the sequence $(1,1)$ is $20$ and the weight of the sequence $(1,3)$ is $11$. For $1\leq v\leq n$, define $s_ v$ as the smallest possible weight of a good sequence containing the value $v$.
Your task is to determine the values $s_1,\ldots ,s_ n$.
Input
The first line of input consists of the integer $n$, the number of weights. The next $n$ lines contain the integer weights $w_1, \ldots , w_ n$.
Output
Print $n$ lines containing $s_1$, $\ldots $, $s_ n$ in order.
Constraints and Scoring
We always have $1\leq n \leq 30\, 000$ and $1\leq w_ i \leq 10^6$ for each $1\leq i \leq n$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.
|
Group |
Points |
Constraints |
|
$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$ |
No additional constraints |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 42 1 |
10 52 53 |
