QTGIFT1 - New year love story

With brother’s help, DB has successed in flirt with TN. (see QTNOEL). But now he has another problem :

In Vietnamese Tet holidays (Vietnam’s Lunar New Year), there is a custom called ‘Li xi’ that adult give children money in red packs, to wish them strong and happy. DB’s family has a very special method to give children Li xi :

There are n Li xi packs, every pack has a[i] VND – Vietnamese unit of money, and a random positive integer k (1 ≤ k ≤ n). DB can take any pack, but mustn’t take k packs in a row.

Let’s help him to find the way to take the maximum of money.

Input :

-          First line : two integer n and k

-          Second line : n integer, the i-th number is a[i]

Output :

            A single number s – the maximum money DB can take.

Example:

Input:

5 3

6 19 8 7 13

 

Output:

45

Limit :

- 0 ≤ a[i] ≤ 2000

- n ≤ 106

 


Added by:Coder nhà mình
Date:2014-01-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Tài liệu chuyên tin

hide comments
2018-12-14 16:41:25
Test cases are extremely weak, my worst case O(n^3) solution gave AC
2017-11-27 16:48:02
This problem is required to be solved with algorithm costing O(N) time complexity. My first O(N log2(N)) solution got TLE.
2017-02-19 12:11:53 Dimitris Rontogiannis
O(n log N) gets TLE, but with fast I/O it gets AC!
2015-03-02 08:51:39 Amit Ajaat
Please explain question correctly. If he can't take 3 packs in a row, in the given testcase then maximum sum is 53 corresponding to all i.e. He may have taken all 5 packs in a row. Isn't it.
2015-01-23 06:53:43 ­
Vietnamese's story is far different from English's =))
2015-01-23 06:53:43 aristofanis
O(n log n) gets TLE... Is there anything faster, or just constant optimisation is required?
EDIT: Never mind, I got AC with a O(n) algo.. Really nice problem!

Last edit: 2014-04-22 16:31:59
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.