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

chunlian Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

chunlian.html

Problem Description

Guangxuan has been shopping for Chunlians during CNY. When he entered the shop, he found N Chunlians hung on the wall, from left to right. Each Chunlian had a certain value Pi.

He needs to buy C Chunlians for his family. Furthermore, due to his laziness, he wants to select the Chunlians such that no two Chunlians (including non-consecutive ones) are more than distance K apart from one another on the wall.

Help Guangxuan determine the maximum value he can obtain.

Input

The first line of input will contain three integers, N, C and K.

The second line of input will contain N integers, representing the array P.

Output

The output should contain one integer, representing the maximum value Gug can obtain.

Limits

For all subtasks: 1 ≤ C ≤ N, C - 1 ≤ K < N, 1 ≤ Pi ≤ 109.

Subtask 1 (13%): 1 ≤ N ≤ 20.

Subtask 2 (15%): 1 ≤ N ≤ 200.

Subtask 3 (17%): 1 ≤ N ≤ 1000.

Subtask 4 (12%): 1 ≤ N ≤ 300000, 1 ≤ Pi ≤ 2.

Subtask 5 (14%): 1 ≤ N ≤ 300000, 1 ≤ C ≤ 2.

Subtask 6 (29%): 1 ≤ N ≤ 300000.

Subtask 7 (0%): Sample Testcases

Sample Testcase 1

Input

5 2 3
8 1 2 3 5

Output

11

Sample Testcase 2

Input

7 3 4
5 7 1 6 3 5 9

Output

20

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
113201s256MBMinimum
215401s256MBMinimum
317601s256MBMinimum
412201s256MBMinimum
514201s256MBMinimum
6291201s256MBMinimum
7021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o chunlian -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.