TopCoder

Caido
主唱太拼命了

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

33.3% (16/48)

Tags

Description

N 個數字 a1,a2,,aN,以及兩個常數 K,b,你必須要選擇一些數字 L1,L2,,LM,滿足:

  • 1=L1<L2<L3<<LM=N
  • Li+1LiKi[1,M1]

你得到的分數會是:

i=1MaLibi=1M1(Li+1Li)2

請你最大化此分數。

Input Format

輸入的第一行包含三個整數 N,K,b,分別代表序列的長度,以及兩個常數。

接下來的一行,包含 N 個整數,分別是 a1,a2,,aN

  • 2N5×105
  • 1KN
  • 109ai109
  • 0b105

Output Format

輸出一個整數於一行,代表最大的分數。

Sample Input 1

5 2 0
-1 -2 -3 -4 -5

Sample Output 1

-9

Sample Input 2

7 7 1
-4 -2 4 -3 2 5 4

Sample Output 2

1

Sample Input 3

8 3 5
3 1 4 1 5 9 2 6

Sample Output 3

-4

Hints

Problem Source

IOICamp 2022 Day3 pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0, 3~12 b=0 80
3 1, 13~27 b0,K=N 80
4 0~37 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 4
1 1000 262144 65536 1 3 4
2 1000 262144 65536 1 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 3 4
14 1000 262144 65536 3 4
15 1000 262144 65536 3 4
16 1000 262144 65536 3 4
17 1000 262144 65536 3 4
18 1000 262144 65536 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 4
29 1000 262144 65536 4
30 1000 262144 65536 4
31 1000 262144 65536 4
32 1000 262144 65536 4
33 1000 262144 65536 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4