oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

cardgame Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Peanut is playing a card game today, and in this card game, Bradley deals him a set of N cards in a row and lays them in a row from left to right. Each of this card contains an integer, which can be positive or negative. Bradley then asks Peanut to select up to K non-overlapping ranges of length up to L. He then has to pick up those cards and sum them. Help Peanut find the maximum sum.

Input

The first line of input contains three integers, N, K and L.
The second line of input contains N integers, which represent the cards given to Peanut by Bradley.

Output

Your program should output one integer, stating the maximum sum Peanut can obtain.

Limits

1 ≤ N, K, L ≤ 3 000.
Each of the integers on the cards will not have an absolute value of more than 100 000.
Subtask 1 (3%): All integers in the cards will be non-negative. L = N.
Subtask 2 (11%): K = 1, L = N.
Subtask 3 (14%): K = 1.
Subtask 4 (25%): 1 ≤ N, K, L ≤ 200.
Subtask 5 (47%): No other constraints apply.
Subtask 6 (0%): Sample testcases.

Sample Input 1

7 1 7
5 -9 3 -2 5 5 -3 

Sample Output 1

11

Explanation for Sample 1

5 -9 (3 -2 5 5) -3

Sample Input 2

10 3 3
1 -2 3 4 8 -6 7 -8 9 -10 

Sample Output 2

31

Explanation for Sample 2

1 -2 (3 4 8) -6 (7) -8 (9) -10

Tags

Dynamic Programming, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13201s256MBMinimum
211201s256MBMinimum
314201s256MBMinimum
425201s256MBMinimum
547201s256MBMinimum
6021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o cardgame -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.