TopCoder

Caido
主唱太拼命了

User's AC Ratio

93.5% (29/31)

Submission's AC Ratio

65.3% (49/75)

Tags

Description

水源阿伯是指臺灣臺北市臺灣大學水源校區的拖吊違停腳踏車的工友,因為他們總是穿著藍色工作服,戴著安全帽,工作認真,因此被學生們稱為「水源阿伯」。

水源阿伯的工作是負責拖吊水源校區內的違停腳踏車。由於水源校區是臺大最大的校區,學生人數眾多,因此違停腳踏車的問題一直是校方和附近住戶頭痛的問題。水源阿伯的出現,有效改善了水源校區的交通秩序,也讓學生們學會遵守交通規則。

水源阿伯們工作認真,風雨無阻,受到了學生們的尊敬。他們的形象也曾經被拍成紀錄片,在網路上引起熱議。

水源阿伯們是臺灣社會的縮影,他們默默地工作,為社會做出了貢獻。他們的故事也告訴我們,只要有責任心,認真工作,就能夠得到大家的肯定。

---Google Bard

有一天, wcwu 打完球後將腳踏車停在系館門口,打算去系館放球具的同時投一杯飲料喝。就在 wcwu 開開心心的拿著 FIN 走出系館時,赫然發現他臨停在系館門口的 ubike 已經不見蹤跡,只在地上看到用白色粉筆寫的 「吊水源」三個大字! wcwu 只好徒步走到 google 評價 1.3 顆星的水源拖吊場,正當他想要向工作認真的水源阿伯贖回 ubike 時,卻發現他沒帶錢!情急之下, wcwu 承諾幫水源阿伯解決他的一個煩惱,水源阿伯發現 wcwu 認識 IOIC 的學員後,立馬請 wcwu 解決一個困擾他許久的問題。

水源阿伯每天都可以自己拖吊 $m$ 輛腳踏車,被拖吊的腳踏車用來供應給腳踏車行,接下來的 $n$ 天內,第 $i$ 天水源阿伯需要提供給腳踏車行 $d_i$ 輛腳踏車。為了每天都滿足腳踏車行的需求,水源阿伯會雇用一位工讀生幫忙自己拖吊更多的腳踏車,除了每天阿伯自己拖吊的腳踏車以外,水源阿伯每請這位工讀生拖吊一輛腳踏車就需要付額外的 $c$ 元。另外,如果水源阿伯和工讀生拖吊太多輛腳踏車,他們就需要額外租用空地來放置腳踏車,存放 $j$ 輛腳踏車每天需花費 $a\cdot j$ 元。水源阿伯想知道他每天自己和工讀生這 $n$ 天內分別需要拖吊幾輛腳踏車,才可以花最少額外的支出來達到腳踏車行的要求。

wcwu 把這個問題交給上過 IOIC 課程的你,請你儘快幫他解決問題,不然他要被 ubike 扣錢扣到破產了!

Input Format

輸入的第一行包含四個整數 $n, m, a, c$,變數意義與題目敘述相同。

第二行包含 $n$ 個非負整數 $d_i$,變數意義與題目敘述相同。

  • $1\leq n\leq 1000$
  • $0\leq m\leq 100$
  • $1\leq a\leq 10^ 5$
  • $1\leq c\leq 10^ 5$
  • $0\leq d_i\leq 100$
  • $\sum d_i \leq 100$

Output Format

輸出第一行包含一個整數 $cost$,代表水源阿伯在達成腳踏車行要求下所需最小額外花費。

輸出的第二行包含 $n$ 個整數 $ans_i$,代表第 $i$ 天需要拖吊的腳踏車數。

如果有多組答案 $ans_i$ 使得最小額外花費相同,輸出其中一組即可。

答案必須滿足 $0\le ans_i\le 100$。

如果輸出的最小額外花費正確,並且有依照正確格式輸出 $ans_i$,但構造的 $ans_i$ 無法得到最小額外花費,可以拿到 50 分。

Sample Input 1

5 2 1 2
0 0 0 0 10

Sample Output 1

14
0 0 0 2 8

Sample Input 2

6 2 2 10
5 1 4 0 3 6

Sample Output 2

78
5 2 3 2 2 5

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~38 無特別限制 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
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
32 1000 524288 65536 2
33 1000 524288 65536 2
34 1000 524288 65536 2
35 1000 524288 65536 2
36 1000 524288 65536 2
37 1000 524288 65536 2
38 1000 524288 65536 2