P2672 [NOIP 2015 Junior] Salesman

NOIP 2015 Junior T4.

A Ming is a salesman. He is assigned to promote his company’s products on Screw Street. Screw Street is a dead-end; the exit and entrance are the same. One side of the street is a wall, and the other side has households. There are $N$ households on Screw Street, and the $i$-th household is $S_i$ meters from the entrance. Because multiple households can live in the same building, several households may be at the same distance from the entrance. A Ming will enter from the entrance, promote products to $X$ households on Screw Street one by one, and then walk back along the same route. For every $1$ meter he walks, he accumulates $1$ fatigue point. Promoting to the $i$-th household accumulates $A_i$ fatigue points. A Ming is a workaholic. He wants to know, for different values of $X$, under the premise of not walking any extra distance, what is the maximum total fatigue he can accumulate.

The first line contains a positive integer $N$, the number of households on Screw Street. The next line contains $N$ non-negative integers; the $i$-th integer $S_i$ is the distance from the $i$-th household to the entrance. It is guaranteed that $S_1 \le S_2 \le \cdots \le S_n

Output $N$ lines, each with one positive integer. The integer on the $i$-th line denotes the maximum total fatigue when $X=i$.

Explanation for Sample 1: $X=1$: promote to household $5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $5$, and the total fatigue is $15$. $X=2$: promote to households $4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $4+5$, and the total fatigue is $5+5+4+5=19$. $X=3$: promote to households $3,4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $3+4+5$, and the total fatigue is $5+5+3+4+5=22$. $X=4$: promote to households $2,3,4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $2+3+4+5$, and the total fatigue is $5+5+2+3+4+5=24$. $X=5$: promote to households $1,2,3,4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $1+2+3+4+5$, and the total fatigue is $5+5+1+2+3+4+5=25$. Explanation for Sample 2: $X=1$: promote to household $4$. The round-trip walking fatigue is $4+4$, the promotion fatigue is $4$, and the total fatigue is $4+4+4=12$. $X=2$: promote to households $1,4$. The round-trip walking fatigue is $4+4$, the promotion fatigue is $5+4$, and the total fatigue is $4+4+5+4=17$. $X=3$: promote to households $1,2,4$. The round-trip walking fatigue is $4+4$, the promotion fatigue is $5+4+4$, and the total fatigue is $4+4+5+4+4=21$. $X=4$: promote to households $1,2,3,4$. The round-trip walking fatigue is $4+4$, the promotion fatigue is $5+4+3+4$, and the total fatigue is $4+4+5+4+3+4=24$. Or promote to households $1,2,4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $5+4+4+1$, and the total fatigue is $5+5+5+4+4+1=24$. $X=5$: promote to households $1,2,3,4,5$. The round-trip walking fatigue is $5+5$, the promotion fatigue is $5+4+3+4+1$, and the total fatigue is $5+5+5+4+3+4+1=27$. Constraints: For $20\%$ of the testdata, $1 \le N \le 20$. For $40\%$ of the testdata, $1 \le N \le 100$. For $60\%$ of the testdata, $1 \le N \le 1000$. For $100\%$ of the testdata, $1 \le N \le 100000$. Translated by ChatGPT 5