StoneGame
SRM 345 · 2007-04-21 · by rusolis
Problem Statement
You and your friend are playing a game. There is a number of treasure chests hidden under piles of stones. That is, the i-th chest has stones[i] stones piled on top of it. You take turns taking exactly one stone from the top of one of the chests. Whoever takes the last stone from the top of a chest takes the chest and the treasure inside. The inside of the i-th chest is worth treasure[i]. The game objective is to gather as much treasure as possible.
Unfortunately, your friend is a cyborg and always makes the best possible move (maximizing his final win). Given stones and treasure, return the maximum total amount you can get from the chests given that you move first.
Constraints
- stones will contain between 1 and 50 elements, inclusive.
- stones and treasure will contain the same number of elements.
- Each element of stones will be between 1 and 10^6, inclusive.
- Each element of treasure will be between 1 and 10^6, inclusive.
{3,2}
{1,2}
Returns: 5
In your first move you take the stone from the 0-th chest and take its treasure. Then your friend must take a stone from the 1-st chest leaving you with one stone on the 1-st chest. You take the last stone in your second move and take the contents of the 1-st chest.
{5,4,3,2,1}
{1,1,1,1,1}
Returns: 9
{5,5}
{2,2}
Returns: 0
{1}
{10}
Returns: 0
{5,4,15,457,345,13,235,346}
{2,3,1,4,5,1,3,2}
Returns: 1407
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class StoneGame with a public method int getScore(vector<int> treasure, vector<int> stones) · 127 test cases · 2 s / 256 MB per case