Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Bowling for Numbers++
Description Recall that at the Canadian Carnival Competition (CCC), a popular game was Bowling for Numbers. A large number of bowling pins were lined up in a row. Each bowling pin had a number printed on it, which was the score obtained from knocking over that pin. The player was given a number of bowling balls; each bowling ball was wide enough to knock over a few consecutive and adjacent pins. For example, one possible sequence of pins was: 2 8 5 1 9 6 9 3 2 If Alice was given two balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would be 39, the sum of two throws: 2+8+5 = 15, and 9+6+9 = 24. Since many, including you, have mastered the art of throwing balls at pins, the old and wise members of the Canadian Carnival Competition Committee have decided to make the game slightly more difficult by introducing the concept of Penalty pins are pins with a 2 8 -5 3 5 8 4 8 -6 If Alice was given three balls, each able to knock over three adjacent pins, the maximum score Alice could achieve would be 38, the sum of three throws: 2 + 8, 3 + 5 + 8, and 4 + 8. Alice's first throw is deliberately to the left and catches only the leftmost two pins, avoiding the -5. Alice's second throw hits 3 5 8, and her third throw catches the remaining 4 8, going through the space created by her second throw to avoid the -6. Bob has a strategy where he picks the shot that gives him the most score, then repeatedly picks the shot that gives him the most score from the remaining pins. This strategy doesn't always yield the maximum score, but is close. On the test data, such a strategy would get a score of 20%. Input Input consists of a series of test cases. The first line of input is The first line of each test case contains three integers. First is the integer The next Output For each test case, output the maximum achievable score by the player. This score is guaranteed to be less than one billion. Sample Input 2 9 2 3 2 8 5 1 9 6 9 3 2 9 3 3 2 8 -5 3 5 8 4 8 -6 Sample Output 39 38 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator