183 . 最大連續和

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

83.3% (10/12)

Submission's AC Ratio

29.6% (32/108)

Tags

ioicamp ioicamp-2022

Description

給你一個序列 $a_1, a_2, \dots, a_N$ 以及一個常數 $K$，請你算出：在至多拔掉 $K$ 個元素的情況下，新序列的最大連續和的最大值。

最大連續和可以是一個空的序列，定義這樣子的連續和的值為 $0$。

Input Format

輸入的第一行包含兩個整數 $N, K$，代表序列的長度，以及你可以移除掉的數量。

接下來的一行，包含 $N$ 個整數 $a_1, a_2, \dots, a_N$，代表序列的內容。

  • $1 \leq N \leq 10^ 5$
  • $0 \leq K \leq N$
  • $-10^ 9 \leq a_i \leq 10^ 9$

Output Format

輸出一個整數於一行，代表新序列最大連續和的最大值。

Sample Input 1

5 1
-1 3 -7 -1 2

Sample Output 1

4

Sample Input 2

3 0
-1 -2 -3

Sample Output 2

0

Sample Input 3

8 3
-3 1 -4 1 -5 9 -2 6

Sample Output 3

17

Sample Input 4

3 0
1000000000 1000000000 1000000000

Sample Output 4

3000000000

Hints

Problem Source

IOICamp 2022 Day4 pF

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~9 $K \leq 50$ 25
3 0~14 無額外限制 75

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 1048576 65536 1 2 3
1 1500 1048576 65536 1 2 3
2 1500 1048576 65536 1 2 3
3 1500 1048576 65536 1 2 3
4 1500 1048576 65536 2 3
5 1500 1048576 65536 2 3
6 1500 1048576 65536 2 3
7 1500 1048576 65536 2 3
8 1500 1048576 65536 2 3
9 1500 1048576 65536 2 3
10 1500 1048576 65536 3
11 1500 1048576 65536 3
12 1500 1048576 65536 3
13 1500 1048576 65536 3
14 1500 1048576 65536 3
Submit
Back to Top