TopCoder

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

54.5% (6/11)

Tags

Description

小波有一座城堡,他每天都在他的城堡裡過著快樂的日子,直到有一天,他的城堡被小奕攻擊了。在小奕攻擊小波的城堡時,城堡的某一面城牆居然被小奕完全摧毀了!剛好小波覺得這面城牆本來就長得很醜,正好可以重新建造一次這面城牆。

這面城牆的寬度是 $N$ 公尺,他將整面城牆劃分成 $N$ 個寬 1 公尺的區塊,由左至右從 1 到 $N$ 編號,並且訂購了 $Q$ 個寬度為 1、厚度和城牆一樣、高度不等的石磚,一個石磚必須剛好放進一個區塊之中,不能跨越多個區塊,也不能旋轉。正式地說,這 $N$ 個區塊有各自的高度,一開始高度都是 0,如果一個區塊本來的高度是 $x$,接著小波在這個區塊多放一個高度為 $y$ 的石磚,在這之後這個區塊的高度會變成 $x+y$。

小波訂購的 $Q$ 個石磚會依序送達,第 $i$ 個石磚的高度是 $h_i$,然而小波在拿到石磚之前,都不會知道他訂購的石磚高度究竟是多少,他又迫不及待地想要看到城牆蓋好的樣子,因此他每收到一個石磚,就要立刻選一個區塊來放。他選擇區塊的原則是這樣的:如果目前第 $i$ 個區塊的高度是 $x_i$,那這面城牆的醜度就是
$$
\sum_ {k=0}^ {N} (x_k-x_{k+1})^ 2
$$
特別地,$x_0=x_{N+1}=0$。小波希望選擇一個區塊放置這個石磚,使得放下去之後,這面城牆的醜度盡量小。如果有多個區塊都會讓醜度最小,他會選擇編號最小的區塊。

舉例來說,$N=5$、$Q=10$,10 個石磚的高度依序是 $3,1,4,1,5,9,2,6,5,3$。在放第一個石磚的時候,無論放在哪裡,放下後的醜度都會是 18,因此小波會將第一個石磚放在第 1 個區塊。在放第二個石磚的時候,放在區塊 1 的話醜度會是 32、放在區塊 2 的話醜度會是 14、放在其他區塊則會是 20,因此小波會將第二個石磚放在區塊 2。過程中每個區塊的高度變化如下圖,紅色的石磚代表剛放下去的石磚,下方的數字代表該區塊的高度。

小奕偷偷知道了這 $Q$ 個石磚的高度,他很好奇小波新蓋的城牆會長什麼樣子,以便規劃下一次的攻城行動,請你告訴小奕最終每個區塊的高度會是多少。

Input Format

第一行有一個整數 $N,Q$,分別代表城牆的寬度與石磚的數量。

第二行有 $Q$ 個以空白間隔的整數 $h_1,h_2,\dots,h_Q$,代表 $Q$ 個依序送達的石磚的高度。

  • $1 \leq N,Q \leq 500$
  • $1 \leq h_i \leq 10^ 5$

Output Format

輸出 $N$ 個以空白間隔的整數 $x_1,x_2,\dots,x_N$,代表第 $i$ 個區塊最終的高度是 $x_i$。

Sample Input 1

5 10
3 1 4 1 5 9 2 6 5 3

Sample Output 1

3 8 11 9 8

Sample Input 2

3 4
100000 100000 100000 100000

Sample Output 2

100000 200000 100000

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2