Advertisement blocking software were detected ;( Please add this webpage to whitelist.

RPLB - Blueberries

no tags 

Teresa picked up enough strawberries, now she wants to pick blueberries from the magical blueberry bush from Rainbowland.


Knowing her previous experience with the strawberries, Teresa wants to pick up the blueberries in a way that she may not exceed the limit proposed.


When picking the blueberries, she noticed that if she pick from the bush i, she couldn't pick the blueberries at the bush i+1 (some sort of magic in rainbowland).


Worried about this, Teresa wants to know the maximum blueberries she can pick, given the number of bushes and the number of blueberries in each bush.



Will contain an integer T, then, T cases will follow, each case starts with a number N and K, being N the number of bushes and K the number of blueberries Teresa will pick as maximum, the next line contains N integers, each one representing the blueberries there is on the i-th bush.



You will output for each test case the string: “Scenario #i: “ where i is the test case you are analyzing, then, an integer denoting the maximum number of blueberries you can grab.





5 100

50 10 20 30 40


5 87

21 45 30 12 14

Scenario #1: 90

Scenario #2: 65


Blank line between test cases for clarification and separation”

Output explanation (first scenario)

Teresa picks the 1st blueberry bush (50), she cannot pick the 2nd, she decides not to pick until the 5th one where she picks the “40” blueberry, she could pick the 3rd bush, but she would exceed the limit (100).

Output explanation (second scenario)

Teresa picks the 1st, the 3rd and the 5th bush, total of (21+30+14 = 65) blueberries



1<=N<=1000; 1<=K<=1000

Added by:david_8k
Time limit:0.439s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Resource:Own Problem used for the RPL contest

hide comments
Mayank Garg: 2015-08-19 19:27:09

At last accepted .. silly mistake costed me a WA :p my 150th !! Easy dp !! :-)

harshit sharma: 2015-07-22 18:03:15

good dp....easy 1 :)

Shashank Tiwari: 2015-07-10 11:16:39

Okay , if you are getting wrong answer , then check ...

1. Output has to be of form

Scenario< 1 space>#1:<1 space>90
Scenario< 1 space>#2:< 1 space>65

Also , there is no extra new lines between each scenario output. All of them has to be in the immediate new line.

2. Int data type will suffice.

Input :


5 20
100 200 300 400 500

4 10
2 8 3 4

1 1

8 100
40 10 3 5 8 100 20 7

Output :
Scenario #1: 0
Scenario #2: 8
Scenario #3: 1
Scenario #4: 100

5. Hint : this is 0-1 Knapsack problem . Use dynamic programming

6. You can start picking from any bush not necessarily first but once you pick a berry , you have to pick all berries from same bush.

Last edit: 2015-07-10 12:38:08
thewatch: 2015-06-10 22:05:05

Nice Problem!! My 100th!!

AlphaDecay: 2015-06-09 16:35:00

Nice One !

Shashank Gupta: 2015-04-09 03:36:22

Nice problem ... Think DP :D

freaker: 2014-12-15 16:15:24

nice DP problem for beginners like me ...

Last edit: 2014-12-15 16:18:53
Rohan Jain: 2014-12-06 19:51:26


AlcatraZ: 2014-08-30 21:30:56

Good problem .. Take care of output format though.

Shantanu Singh: 2014-07-01 13:06:44

At last phew... My first DP :D ..Took a lot of time but finally got it correct ;)