AMR11C - Robbing Gringotts

no tags 

 

The Death Eaters are low on funds, and their leader Voldemort has asked them to get more money quickly, or face his wrath.  They decide that the best way is to rob Gringotts Wizarding Bank.  
By threatening one of the goblins in charge of the bank, the 'M' Death Eaters have discovered that Gringotts has 'N' vaults, with vault number 'i' containing  X[i] gold items.  The weights of the gold items in the ith vault are g[i][1],g[i][2],...,g[i][X[i]]. But as soon as a vault is robbed, the magical wards go off and alarm bells ring. Thus they have enough time to rob just one vault each, and all robberies have to take place at the same time. The Death Eaters have decided that no two of them will rob the same vault as this increases the chances of them being caught.
Death Eater j has a bag which can hold weight v[j]. They are a greedy and cowardly lot, so a Death Eater will only agree to rob a vault if he can fill up his bag completely to its capacity by taking some subset of the objects present in that vault. Note that it is not possible for a Death Eater to break any gold item; either it should be taken fully, or not be taken.
Find the maximum weight of gold they can take away by planning their strategy correctly. 
Input (STDIN):
The first line contains the number of test cases T. T test cases follow. Each test case contains integers M and N on the first line. The next line contains M integers, the jth of which is v[j], which is the maximum weight of gold the jth Death Eater's bag can hold. The following N lines describe the gold items in the vaults. The ith line contains X[i], the number of gold items present in the ith vault, followed by X[i] integers g[i][1]..g[i][X[i]], denoting the weights of the each of the items present in the ith vault. There is a blank line after each test case.
Output (STDOUT):
Output one line for each test case, containing the maximum total weight of gold that the Death Eaters can rob.
Constraints:
1 <= T <= 10
1 <= N,M <= 50
1 <= X[i] <= 25
1 <= v[i],g[i][j] <= 10,000,000
Time Limit: 10 s
Memory Limit: 64 MB
Sample Input:
2
2 3
3 9
2 4 5
2 3 9
1 10
4 4
3 7 8 10
3 1 2 4
2 3 7
4 2 2 4 4
1 3
Sample Output:
12
28

 

The Death Eaters are low on funds, and their leader Voldemort has asked them to get more money quickly, or face his wrath.  They decide that the best way is to rob Gringotts Wizarding Bank.  

 

By threatening one of the goblins in charge of the bank, the 'M' Death Eaters have discovered that Gringotts has 'N' vaults, with vault number 'i' containing  X[i] gold items.  The weights of the gold items in the ith vault are g[i][1],g[i][2],...,g[i][X[i]]. But as soon as a vault is robbed, the magical wards go off and alarm bells ring. Thus they have enough time to rob just one vault each, and all robberies have to take place at the same time. The Death Eaters have decided that no two of them will rob the same vault as this increases the chances of them being caught.

 

Death Eater j has a bag which can hold weight v[j]. They are a greedy and cowardly lot, so a Death Eater will only agree to rob a vault if he can fill up his bag completely to its capacity by taking some subset of the objects present in that vault. Note that it is not possible for a Death Eater to break any gold item; either it should be taken fully, or not be taken.

 

Find the maximum weight of gold they can take away by planning their strategy correctly.

 

Input (STDIN):

The first line contains the number of test cases T. T test cases follow. Each test case contains integers M and N on the first line. The next line contains M integers, the jth of which is v[j], which is the maximum weight of gold the jth Death Eater's bag can hold. The following N lines describe the gold items in the vaults. The ith line contains X[i], the number of gold items present in the ith vault, followed by X[i] integers g[i][1]..g[i][X[i]], denoting the weights of the each of the items present in the ith vault. There is a blank line after each test case.

 

Output (STDOUT):

Output one line for each test case, containing the maximum total weight of gold that the Death Eaters can rob.

 

Constraints:

1 <= T <= 10

1 <= N,M <= 50

1 <= X[i] <= 25

1 <= v[i],g[i][j] <= 10,000,000

 

Sample Input:

2

2 3

3 9

2 4 5

2 3 9

1 10

 

4 4

3 7 8 10

3 1 2 4

2 3 7

4 2 2 4 4

1 3

 

Sample Output:

12

28

 

 


hide comments
Dip: 2013-01-14 20:30:33

On the best solution page of this problem, best time is 13.21 sec and here I see that the time limit is 10s. ????

foreverbell: 2013-01-03 11:48:58

Note that the perfect matching of the left side may not exist.

Buda IM (retired): 2012-01-08 11:42:58

There is no way to pass the TL for worst case on spoj servers. TL is too strict

[Rampage] Blue.Mary: 2011-12-20 16:47:51

if he can fill up his bag ***completely***

Nikhil Garg: 2011-12-19 16:06:25

Considering spoj servers, time limit is probably a little tight.


Added by:Varun Jalan
Date:2011-12-15
Time limit:1.370s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Varun Jalan - ICPC Asia regionals, Amritapuri 2011