BSSPC '21 S3 - James's Egirl Discord Status

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

James, being the egirl he is, likes to set quirky and cool messages as his Discord status!

James has a new Discord status he wants to use for a single contiguous (possibly empty) range of days within the next N days. He knows that using his new status on the i^{th} day will net him a_i egirl points and that days for which he does not use his new status will not affect his egirl points. Note that a_i may be negative.

Furthermore, because James is quirky and cool, the number of days for which the new status is applied must be a multiple of a given positive integer K.

Find the maximum number of egirl points James can gain within the next N days from using his new status!

Constraints

1 \le N \le 10^6

1 \le K \le N

-10^9 \le a_i \le 10^9

Subtask 1 [5%]

1 \le N \le 5\times10^3

Subtask 2 [15%]

1 \le N \le 10^5

1 \le K \le 10

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line contains two integers, N and K.

The next line contains N integers, the values of a_i.

Output Specification

Output a single integer, the maximum number of egirl points James can gain by using his new Discord status on a contiguous subsequence of the next N days, where the number of days for which the status is applied is a multiple of K.

Sample Input 1

5 2
1 3 2 -4 3

Sample Output 1

5

Explanation for Sample 1

James uses his new Discord status on days 2 and 3, netting 3 + 2 = 5 egirl points.

Sample Input 2

4 3
1 2 -69 8

Sample Output 2

0

Explanation for Sample 2

James chooses not to apply his new Discord status at all, netting 0 egirl points.


Comments

There are no comments at the moment.