TopCoder problem "KiwiJuice" used in Member SRM 478 (Division I Level Two)



Problem Statement

    Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. Each bottle has a capacity of C liters, and he poured bottles[i] liters of kiwi juice into the i-th bottle initially. Taro will sell these bottles after performing an arbitrary number of operations of the following type (possibly zero). In each operation, he chooses two distinct bottles A and B, and pours kiwi juice from bottle A to bottle B until either bottle A becomes empty or bottle B becomes full, whichever happens earlier.



If a bottle contains x liters of kiwi juice at the end (where x is an integer between 0 and C, inclusive), then Taro can sell the bottle for prices[x] dollars. Return the maximum amount of money he can earn.



 

Definition

    
Class:KiwiJuice
Method:theProfit
Parameters:int, int[], int[]
Returns:int
Method signature:int theProfit(int C, int[] bottles, int[] prices)
(be sure your method is public)
    
 

Constraints

-C will be between 1 and 49, inclusive.
-bottles will contain between 1 and 15 elements, inclusive.
-Each element of bottles will be between 0 and C, inclusive.
-prices will contain exactly C + 1 elements.
-Each element of prices will be between 0 and 1,000,000, inclusive.
 

Examples

0)
    
10
{5, 8}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10}
Returns: 10
If Taro pours kiwi juice from bottle 0 to bottle 1, then bottle 0 will contain 3 liters of kiwi juice and bottle 1 will contain 10 liters of kiwi juice. He can sell bottle 1 for 10 dollars.
1)
    
10
{5, 8}
{0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 10}
Returns: 20
Sell both bottles without pouring.
2)
    
10
{4, 5, 3, 7}
{14, 76, 12, 35, 6, 94, 26, 3, 93, 90, 420}
Returns: 625
It is possible that a bottle containing lesser juice is more expensive.
3)
    
1
{0}
{1000000, 1000000}
Returns: 1000000
4)
    
49
{2, 47, 24, 14, 0, 32, 9, 12, 31, 46, 39, 12, 16, 22, 29}
{428668, 995687, 128567, 37241, 496916, 238624, 304781, 997819, 85856, 417008,
398570, 951499, 750349, 333625, 927594, 188616, 942498, 259414, 654344, 354809,
25303, 226854, 98578, 207140, 305527, 358343, 393213, 256248, 282644, 103327,
667191, 103402, 609183, 619323, 189127, 518006, 778846, 400460, 128334, 795097,
605203, 669142, 121825, 934404, 837430, 554265, 610818, 546228, 80784, 949440}
Returns: 12873962

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11019

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14187&pm=11019

Writer:

rng_58

Testers:

liympanda , konqueror , ivan_metelsky , keshav_57

Problem categories:

Dynamic Programming, Math