OTHS Coding Competition 1 (Mock CCC) J4 - Railgun

View as PDF

Submit solution


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

Author:
Problem types

Misaka is fighting against an enemy army consisting of N robots standing in a row, with the i^{th} robot having a power of p_i. Misaka wants to weaken the enemy army as much as possible by destroying powerful robots, but she can only attack from either the left side or the right side. Fortunately, she has a powerful ability called Railgun that can destroy the S leftmost robots or the S rightmost robots. If there are fewer than S robots left, using the ability will destroy all of them.

After using her Railgun ability at most T times, by how much can she weaken the enemy army's power?

Constraints

1 \le N \le 10^6

1 \le S, T \le N

1 \le p_i \le 2000

ST < 10^9

Subtask 1 [2/15]

1 \le N \le 2000

The robots are sorted in non-decreasing order in terms of power.

Subtask 2 [9/15]

1 \le N \le 2000

N is divisible by S.

Subtask 3 [4/15]

No additional constraints.

Input Specification

The first line of input contains 3 space separated integers, N, S, and T.

The second line of input containts N space separated integers, the power of each robot.

Output Specification

Output a positive integer, the sum of the destroyed robots' powers.

Sample Input 1

5 2 1
1 2 3 4 5

Sample Output 1

9

Explanation for Sample Output 1

Misaka can destroy the 2 leftmost robots or the 2 rightmost robots. She can weaken the enemy army more by destroying the 2 rightmost robots (4 + 5 = 9).

Sample Input 2

10 2 3
10 1 3 2 9 9 8 9 1 1

Sample Output 2

37

Explanation for Sample Output 2

To attack optimally, Misaka first destroys the 2 rightmost robots.

The robots' powers now become: 10, 1, 3, 2, 9, 9, 8, 9

Then, she destroys the 2 rightmost robots again.

The robots' powers now become: 10, 1, 3, 2, 9, 9

Finally, she destroys the 2 rightmost robots one more time.

The robots' powers now become: 10, 1, 3, 2

In total, she weakened the army by (1+1)+(8+9)+(9+9)=37.

Sample Input 3

11 4 2
9 4 1 3 2 1 3 2 9 1 1

Sample Output 3

30

Explanation for Sample Output 3

To attack optimally, Misaka first destroys the 4 rightmost robots.

The robots' powers now become: 9, 4, 1, 3, 2, 1, 3

Then, she destroys the 4 leftmost robots.

The robots' powers now become: 2, 1, 3

In total, she weakened the army by (2+9+1+1)+(9+4+1+3)=30.

Sample Input 4

5 4 5
1 1 1 1 1

Sample Output 4

5

Explanation for Sample Output 4

All robots are destroyed no matter how she attacks.


Comments

There are no comments at the moment.