47 . 爆裂魔法

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

20.0% (21/105)

Tags

ioicamp ioicamp-2024

Description

惠惠是非常喜歡爆裂魔法的紅魔族，勵志要成為能夠施放爆裂魔法的大魔法師。

要學會爆裂魔法需要依序完成 $K$ 個階段的學習，也就是說需要完成第 $i$ 個階段才能進行第 $i + 1$ 個階段。而每個階段都需要 $M$ 個早上的練習，並在最後一次學習當天的晚上進行驗收。也就是說，要學會爆裂魔法總共需要 $MK$ 天。

惠惠計劃在接下來的 $N$ 天要學會爆裂魔法，為了花費較少的精力學會爆裂魔法，她先列出了這 $N$ 天哪 $MK$ 天她是有空的，也估計了這 $N$ 天早上練習與晚上驗收分別所需要花費的精力。而在開始學習前，她會先進行以下操作任意次（當然也可以不做）：挑選任兩有空狀態不同的天（也就是一天有空一天沒空）並將兩者的狀態交換，而每操作一次就需要花費 $T$ 的精力。操作完成後她就會用這有空的 $MK$ 天進行學習。

現在惠惠告訴你這些精力值，你能幫助她計算出她最少需要花費多少精力才能學會爆裂魔法嗎？

Input Format

輸入第一行有四個整數 $N, M, K, T$。

輸入第二行有一個長度為 $N$ 的 $\texttt{01}$ 字串 $S$，若 $S_i = \texttt{1}$ 則代表一開始第 $i$ 天惠惠是有空的，否則代表沒有空。

輸入第三行有 $N$ 個整數 $a_1, a_2, \ldots, a_N$，代表第 $i$ 天早上練習所需要花費的精力。

輸入第四行有 $N$ 個整數 $b_1, b_2, \ldots, b_N$，代表第 $i$ 天晚上驗收所需要花費的精力。

  • $1 \leq N, M \leq 500000$
  • $1 \leq K \leq 4$
  • $MK \leq N$
  • $|S| = N$
  • $S_i \in \lbrace 0, 1 \rbrace$
  • $S$ 中恰有 $MK$ 個 $\texttt{1}$
  • $0 \leq a_i, b_i, T \leq 10^ 9$

Output Format

請輸出一行，該行有一個整數，代表惠惠要學會爆裂魔法最少所需花費的精力。

Sample Input 1

8 2 2 1
11011000
7 5 8 4 3 1 6 9
5 3 4 2 4 6 3 1

Sample Output 1

22

Sample Input 2

9 5 1 0
101010101
8 6 4 1 9 7 5 3 2
0 0 0 0 0 0 0 0 0

Sample Output 2

15

Sample Input 3

10 4 1 0
0001111000
5 6 5 6 2 4 8 7 6 3
0 2 1 3 6 4 8 5 9 7

Sample Output 3

20

Sample Input 4

9 2 3 0
111000111
0 0 0 0 0 0 0 0 0
8 6 4 1 9 7 5 3 2

Sample Output 4

8

Sample Input 5

18 3 4 12
100010111111110110
34 69 66 95 68 16 13 18 42 16 28 34 62 16 59 98 21 22
68 67 93 21 95 38 17 66 81 67 98 17 30 95 18 41 45 43

Sample Output 5

503

Hints

在範例測試資料一中，惠惠的最優策略為先將第 $1$ 天與第 $6$ 天的狀態交換，這樣就會在第 $2, 4, 5, 6$ 天早上練習並在第 $4, 6$ 天晚上驗收，總花費為 $22$。

在範例測試資料二中，惠惠的最優策略為在第 $3, 4, 7, 8, 9$ 天早上練習並在第 $9$ 天晚上驗收，總花費為 $15$。

在範例測試資料三中，惠惠的最優策略為在第 $1, 3, 5, 6$ 天早上練習並在第 $6$ 天晚上驗收，總花費為 $20$。

在範例測試資料四中，惠惠的最優策略為在第 $1, 4, 6, 7, 8, 9$ 天早上練習並在第 $4, 7, 9$ 天晚上驗收，總花費為 $8$。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~4 範例測資 0
2 1, 5~9 $b_i = 0, T = 0$ 4
3 2, 5, 10~14 $K = 1, T = 0$ 7
4 3, 5, 15~19 $a_i = 0, T = 0$ 12
5 0~5, 20~26 $1 \leq N \leq 2000$ 19
6 0~5, 20~34 $1 \leq N \leq 100000$ 37
7 0~44 無其他限制 21

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 1048576 65536 1 5 6 7
1 6000 1048576 65536 1 2 5 6 7
2 6000 1048576 65536 1 3 5 6 7
3 6000 1048576 65536 1 4 5 6 7
4 6000 1048576 65536 1 5 6 7
5 6000 1048576 65536 2 3 4 5 6 7
6 6000 1048576 65536 2 7
7 6000 1048576 65536 2 7
8 6000 1048576 65536 2 7
9 6000 1048576 65536 2 7
10 6000 1048576 65536 3 7
11 6000 1048576 65536 3 7
12 6000 1048576 65536 3 7
13 6000 1048576 65536 3 7
14 6000 1048576 65536 3 7
15 6000 1048576 65536 4 7
16 6000 1048576 65536 4 7
17 6000 1048576 65536 4 7
18 6000 1048576 65536 4 7
19 6000 1048576 65536 4 7
20 6000 1048576 65536 5 6 7
21 6000 1048576 65536 5 6 7
22 6000 1048576 65536 5 6 7
23 6000 1048576 65536 5 6 7
24 6000 1048576 65536 5 6 7
25 6000 1048576 65536 5 6 7
26 6000 1048576 65536 5 6 7
27 6000 1048576 65536 6 7
28 6000 1048576 65536 6 7
29 6000 1048576 65536 6 7
30 6000 1048576 65536 6 7
31 6000 1048576 65536 6 7
32 6000 1048576 65536 6 7
33 6000 1048576 65536 6 7
34 6000 1048576 65536 6 7
35 6000 1048576 65536 7
36 6000 1048576 65536 7
37 6000 1048576 65536 7
38 6000 1048576 65536 7
39 6000 1048576 65536 7
40 6000 1048576 65536 7
41 6000 1048576 65536 7
42 6000 1048576 65536 7
43 6000 1048576 65536 7
44 6000 1048576 65536 7
Submit
Back to Top