Get Time

   Problem Statement  

 Problem Statement for LongMansionDiv2

Problem Statement


LYC is the pet dog of Emperor Zhangzj of Yali Empire. Zhangzj has a huge affluence. Besides his palace, he has multiple estates. One of them is the Long Mansion, a famous site in Yali. LYC loves to play. One day, he accidentally enters the labyrinthine Long Mansion.

The mansion can be seen as a grid of N rows, indexed from 0 to (N - 1) from up to down, and M columns, indexed from 0 to (M - 1) from left to right. Initially, LYC is standing on the cell in the top left corner. The exit is in the bottom right corner. In other words, LYC wants to travel from row 0 and column 0 to row (N - 1) and column (M - 1). LYC can walk from one cell directly to another if and only if they share a side. He wants to reach the exit as soon as possible..

Unfortunately, each cell contains some obstacles that slow LYC down. For each cell we know the time LYC needs to spend there while passing through the cell. LYC also needs to spend that amount of time in the initial cell and in the exit cell as well. There is a pattern to the obstacles: each column of the mansion looks the same. In other words, all cells within any given row contain the same obstacle type, and therefore they delay LYC by the same amount of time. For example, the entire first row are some bushes, the entire second row contains some walls, and so on. You are given the times in the int[] t. More precisely, LYC will spend t[i] time in each cell he visits in row i.

You are given one int M, and one int[] t. Return the minimal time LYC needs to spend to reach the exit.



Parameters:int, int[]
Method signature:long minimalTime(int M, int[] t)
(be sure your method is public)


-N will be between 1 and 50, inclusive.
-M will be between 1 and 1,000,000,000, inclusive.
-t will contain exactly N elements.
-Each element of t will be between 1 and 1,000, inclusive.


{1, 2, 1}
Returns: 6

LYC's path can be (0, 0) &rarr (0, 1) &rarr (1, 1) &rarr (2, 1) &rarr (2, 2). The time he spends will be 1 + 1 + 2 + 1 + 1 = 6. Note that the first and last cell count as well.

{3, 2, 4, 2}
Returns: 17

This time, LYC's path can be (0, 0) &rarr (1, 0) &rarr (1, 1) &rarr (1, 2) &rarr (2, 2) &rarr (3, 2) &rarr (3, 3).

{3, 2, 5, 4, 2, 8}
Returns: 32
Returns: 1000000000000
Watch out for overflow.
Returns: 1

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 719 Round 1 - Division II, Level Two