KiwiJuice
Member SRM 478 · 2009-12-03 · by rng_58
Member SRM 478 · 2009-12-03 · by rng_58 · Dynamic Programming, Math
Problem Statement
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.
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.
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)
19
{11, 0, 3, 6, 5, 7, 10, 6, 18, 7, 3, 15, 9, 16, 7}
{1036, 572, 84, 542, 794, 257, 1034, 79, 578, 268, 902, 174, 305, 642, 736, 98, 724, 743, 603, 502}
Returns: 13364
4)
1
{0}
{1000000, 1000000}
Returns: 1000000
Submissions are judged against all 75 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KiwiJuice with a public method int theProfit(int C, vector<int> bottles, vector<int> prices) · 75 test cases · 2 s / 256 MB per case