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 ith day will net him ai egirl points and that days for which he does not use his new status will not affect his egirl points. Note that ai 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

1N106

1KN

109ai109

Subtask 1 [5%]

1N5×103

Subtask 2 [15%]

1N105

1K10

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 ai.

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

Copy
5 2
1 3 2 -4 3

Sample Output 1

Copy
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

Copy
4 3
1 2 -69 8

Sample Output 2

Copy
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.