JOIN
Get Time

   Problem Statement  

 Problem Statement for SpellCards

Problem Statement

    You are playing a card game. In the card game, each card holds a magic spell with two properties: its level and its damage. During the game, you will play some of the cards (possibly none or all of them) to attack your enemy.





Initially, there are n cards. The cards are placed in a row and they are labeled from 0 to n-1, in order. You are given two int[]s: level and damage. For each i, the level of card i is level[i], and its damage is damage[i].





In each turn of the game, you can do one of two possible actions:
  1. Let L be the level and D the damage of the card that is currently the leftmost card in the row. If there are at least L cards in the row, you may play the leftmost card. Playing it deals D damage to your enemy. After you play this card, the first L cards in the row (including the played one) are discarded. That is, the cards currently labeled 0 through (L-1), inclusive, are discarded. The order of the remaining cards does not change.
  2. If you have at least one card, you can take the last card in the row and move it to the beginning. For example, if the row initially contained cards A,B,C,D,E, in this order, after this operation it will contain E,A,B,C,D.
After each turn, the cards are relabeled 0 through x-1, where x is their current count.





Return the maximal total damage you can deal to your opponent.
 

Definition

    
Class:SpellCards
Method:maxDamage
Parameters:int[], int[]
Returns:int
Method signature:int maxDamage(int[] level, int[] damage)
(be sure your method is public)
    
 

Constraints

-level will contain between 1 and 50 elements, inclusive.
-level and damage will contain the same number of elements.
-Each element in level will be between 1 and 50, inclusive.
-Each element in damage will be between 1 and 10,000, inclusive.
 

Examples

0)
    
{1,1,1}
{10,20,30}
Returns: 60
You can play card 0 three times in a row, dealing 10+20+30 = 60 damage.
1)
    
{3,3,3}
{10,20,30}
Returns: 30
Here, it is optimal to start by moving the last card to the beginning of the row. In the second turn we then use the card and deal 30 damage. Afterwards, all three cards are discarded.
2)
    
{4,4,4}
{10,20,30}
Returns: 0
This time you can't use any spell card.
3)
    
{50,1,50,1,50}
{10,20,30,40,50}
Returns: 60
You can use 2 cards with damage 20 and 40.
4)
    
{2,1,1}
{40,40,10}
Returns: 80
5)
    
{1,2,1,1,3,2,1}
{10,40,10,10,90,40,10}
Returns: 170
6)
    
{1,2,2,3,1,4,2}
{113,253,523,941,250,534,454}
Returns: 1918

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 563 Round 1 - Division I, Level Two