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

flamethrower Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

flamethrower.html

Poe the Penguin wants to hasten Global Warming (so that he can stay in the water all day long). Therefore. He is going to burn down the trees in Barr the Bear's orchards.

Barr the Bear's orchard contains a row of N trees, labelled from 1 to N from left to right. Poe the Penguin has a flamethrower. This flamethrower can destory a consecutive sequence of at most K trees.

Poe the Penguin wants to cause as much damage as possible. He knows the cost of planting each tree. Poe the Penguin wants to aim his flamethrower in such a way that the sum of costs of trees he destroys is as high as possible. He wonders what this cost is.

Input

The first line contains two integers, N and K.

The following line contains N positive integers. The ith integer denotes the cost of the tree with label i.

You can assume that 1 ≤ K ≤ N ≤ 1000.

Output

Output the maximum cost of the trees Poe the Penguin can damage..

Sample Input

6 3
5 8 9 2 4 1

Sample Output

22

Sample Explanation

Destroying Trees 1 to 3 cost 5+8+9 = 22. (Maximum Cost)

Destroying Trees 2 to 4 cost 8+9+2 = 19.

Destroying Trees 3 to 5 cost 9+2+4 = 15.

Destroying Trees 4 to 6 cost 2+4+1 = 7.

Tags

Dynamic Programming, Sliding Window

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100101s32MBAverage
2011s32MBAverage

Judge Compile Command

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