TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬當上 IOICamp 總召後的故事。

程式比賽中最重要的莫過於點心了。當然, IOICamp 每天的練習賽也不意外。這天殿壬總共準備了 $N$ 份點心,編號 $1$ 號到 $N$ 號,由左至右、編號由小至大的在長桌上排成了一排,第 $i$ 份點心的好吃程度是 $A_i$ 。不過當然不可能每一份點心都很好吃,因此,有些點心的好吃程度是正的,代表該點心是好吃的,有些點心的好吃程度是負的,代表該點心是難吃的。

為了舒緩大家排隊拿點心時的壅擠程度,殿壬決定將這 $N$ 個點心分為 $K$ 區,每一區都必須包含連續的一些點心。此外,兩個區域之間必須至少相隔 $1$ ,否則就沒有分區的意義了。殿壬當然也不希望有些人會吃到難吃的點心,因此他希望被這 $K$ 區包含的點心的好吃程度總和越大越好!

(具體來說,若殿壬選擇的區域為 $[L_1, R_1], \ldots, [L_K, R_K]$ ,則必須滿足 $L_{i + 1} > R_i + 1, \forall 1 \leq i < K$ 且 $L_i \leq R_i, \forall 1 \leq i \leq K$ ,然後殿壬希望 $\displaystyle\sum_{i = 1}^ {K}{(\sum_{j = L_i}^ {R_i}{A_j})}$ 越大越好。)

不過殿壬很快地又發現,當前的點心順序可能沒辦法安排出很高的好吃程度總和,因此他希望能夠交換一些點心的順序,使得可以規劃出最佳的 $K$ 個區域。由於時間緊迫,殿壬只能對點心們進行至多 $S$ 次操作,每次操作可以選擇 $1 \leq i < j \leq N$ ,然後交換在位置 $i$ 的點心以及在位置 $j$ 的點心。

由於總召殿壬相當忙碌,因此請你幫忙他計算在交換不超過 $S$ 次的情況下,能夠做出的 $K$ 個區域的好吃程度總和最大可以是多少。

Input Format

輸入第一行有三個整數 $N, K, S$ ,代表點心的數量,區域的數量,以及殿壬能進行的交換次數。
接著一行有 $N$ 個整數,第 $i$ 個整數 $A_i$ 代表第 $i$ 個點心的好吃程度。

  • $1 \leq N \leq 10^ 4$
  • $1 \leq K \leq \min(N, 20)$
  • $|A_i| \leq 10^ 6$
  • $0 \leq S \leq 10$

Output Format

若殿壬無法將 $N$ 個點心分成滿足題目要求的 $K$ 個區域的話,輸出 impossible
否則,輸出一個整數代表 $K$ 個區域的好吃程度總和的最大值。

Sample Input

Sample Input 1:
4 2 0
1 2 3 4

Sample Input 2:
4 2 1
1 2 3 4

Sample Input 3:
4 2 0
-1 -2 -3 -4

Sample Input 4:
4 2 1
-1 -2 -3 -4

Sample Input 5:
10 2 1
3 -1 7 -7 2 -6 2 9 -1 -8

Sample Output

Sample Output 1:
8

Sample Output 2:
9

Sample Output 3:
-4

Sample Output 4:
-3

Sample Output 5:
23

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~51 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 1
16 1000 262144 262144 1
17 1000 262144 262144 1
18 1000 262144 262144 1
19 1000 262144 262144 1
20 1000 262144 262144 1
21 1000 262144 262144 1
22 1000 262144 262144 1
23 1000 262144 262144 1
24 1000 262144 262144 1
25 1000 262144 262144 1
26 1000 262144 262144 1
27 1000 262144 262144 1
28 1000 262144 262144 1
29 1000 262144 262144 1
30 1000 262144 262144 1
31 1000 262144 262144 1
32 1000 262144 262144 1
33 1000 262144 262144 1
34 1000 262144 262144 1
35 1000 262144 262144 1
36 1000 262144 262144 1
37 1000 262144 262144 1
38 1000 262144 262144 1
39 1000 262144 262144 1
40 1000 262144 262144 1
41 1000 262144 262144 1
42 1000 262144 262144 1
43 1000 262144 262144 1
44 1000 262144 262144 1
45 1000 262144 262144 1
46 1000 262144 262144 1
47 1000 262144 262144 1
48 1000 262144 262144 1
49 1000 262144 262144 1
50 1000 262144 262144 1
51 1000 262144 262144 1