BAT1 - BATMAN1

" Lucius Fox: This conversation used to end with an unusual request.
Bruce Wayne: I'm retired.
Lucius Fox: Well let me show you some stuff anyway. Just for old time's sake.
"

 

Eight years after Harvey Dent's death, the Dent Act allowed eradication of organized crime. BATMAN has disappeared. Wayne enterprises is unprofitable after Bruce discontinued his fusion reactor project. A masked man called Bane who was trained under Ra's al Ghul captures Gordon. Bane attacks the Gotham Stock Exchange, using Bruce's fingerprints in a transaction that bankrupts Wayne.

Now that Gotham City was heading into deep deep trouble, Its time for BATMAN to return.

However, since the company no longer belongs to Bruce Wayne, Mr. Wayne has very little funds to spend on buying his weaponries. Mr Fox head him to the place where all weapons are stored.  

Now these weapons come in batches properly sealed for safety. Each of these batches will have an unbounded number of weapons of different types. To buy these weapons Wayne initially need to pay the price for opening the seal. Then each of these weapons have a cost and a power rating associated with it.  Mr Wayne needs to spend wisely on it to maximize the power rating using  limited amount of money.

People of Gotham, he needs your help for choosing his weaponries.

Lucius Fox: It has a long uninteresting name. I just took to calling it... The Bat, and yes, Mr. Wayne, it does come in black.

Input

t, number of testcases
integers n m k, n: number of batches, m: number of weaponries per batch, k : Money Wayne can spend on weaponries
n integers giving cost of opening the ith batch
n*m numbers denoting cost of jth object from ith batch
n*m numbers denoting the rating of jth object from ith batch

Output

The maximum power rating Wayne could afford 

Constraint:

1 <= n, m <= 20
k <= 1000
cost[i] <= 20
rating[i] <= 100

Example

Input:
1
2 4 20
3 4
3 2 3 2
3 2 3 5
3 2 3 2
4 5 6 5

Output:
40

Added by:Romal Thoppilan
Date:2013-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2018-10-06 14:26:48
Can it be solved using 2-d DP?
2018-08-18 07:48:16
What is answer for this test case?
1
5 10 300
5 6 8 7 1
40 33 39 45 14 4 41 38 7 33
4 46 45 37 1 19 49 5 19 9
12 35 23 30 8 3 50 29 16 28
45 22 46 26 4 46 10 18 29 16
32 16 15 12 25 16 35 47 7 21
24 25 47 41 2 15 40 17 20 42
49 23 24 11 6 3 37 25 10 36
2 26 3 22 40 37 50 37 47 19
6 48 10 9 42 23 14 50 39 26
27 7 3 42 37 19 41 41 9 35

My code is giving 3606 and that on Spojtoolkit is giving 3589. Which one is correct?
2018-04-09 18:44:23
A couple of notes worth reading :
- you can open any batch and as many you want if you have enough money
- you have unlimited weapons in every batch
- once you open a batch its opened forever
my complexity (n*k^2) if that helps
2017-10-05 23:16:39
How is the example possible? the sum of all the ratings is less than the answer?
2017-08-22 12:51:22
AC IN ONE GO ! PRETTY EASY PROBLEM !
2017-05-30 20:03:11 Sigma Kappa
Not sure if my algo is optimal, but got Accepted after saving time on the DP table initialization. My DP state is at most 2^{21} bits.
2017-05-23 18:50:20 Shubham Jadhav
Thanks @vengatesh15 for the advice :)
2017-03-08 21:38:57 shahzada
Done with top down and bottom up both. Easy One :-D
2017-02-10 17:38:56
Try to correct the question u haven't specified we can take a weapon multiple times
2017-01-24 15:47:20
easy dp :)
cost cannot be 0, otherwise he can buy infinite amount of weapons and max rating would be infinite.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.