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

hide comments
harshh3010: 2021-04-01 22:14:41

O(n*k*m) works fine...
Output for tc provided by @Rafail Loizou is 26, and for the tc provided by @learnerinblack is 3589

asd1232afaax: 2021-03-13 19:46:58

@Rafail Loizou

my solution ouput 26 by input testcase you provided. But got WA. is there something wrong?

Rafail Loizou: 2020-11-14 17:33:16

!!! WARNING !!!
I got AC with O(n*k*k*m). I followed this complexity's logic by looking at the comments.
1d: until which batch we will use.
2d: until how much money we will spend on opening batches.
3d: until which amount of money we will spend in total ( seals + buying weapons from open batches)
But even if this gets AC I found a test cases that makes this solution not work and I bet if you add this it will make most of the solutions submitted not work. Here is the test case:
1
3 1 14

1 1 1

5
3
7

6
3
20
My solution gives answer 23. And I bet most n*k*k solutions do. But the correct answer here is 26. He can open 1st and 3rd batch and buy a cost 5 weapon and a cost 7 weapon giving 26 total rating as the answer. This problem to actually be solvable without WAs like this that the problem setter did not take into consideration needs 2^n * k * m and add the optimizations to figure out a correct time limit. This problem is a joke just do the n*k*k*m WA solution and you will get AC.

jenasomnath: 2020-05-26 21:10:21

Please check id 26046604. I don't know why it's giving WA.

scolar_fuad: 2020-02-29 05:37:38

4Dimention dp problem Nice
learn something new

dkkv0000: 2020-01-25 20:00:31

good problem
top down is <3

the_mist: 2019-11-05 12:39:10

Nice problem !! AC in one go ;p

Last edit: 2019-11-05 12:39:26
hkyiitd: 2019-03-08 17:44:42

Getting TLE with O(n*k*k) algo.

jwalinarora: 2018-10-06 14:26:48

Can it be solved using 2-d DP?

learnerinblack: 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?


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