LongMansionDiv2
SRM 719 · 2017-07-25 · by matthew99a
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
You are given one
Constraints
- 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.
3
{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.
4
{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).
5
{3, 2, 5, 4, 2, 8}
Returns: 32
1000000000
{1000}
Returns: 1000000000000
Watch out for overflow.
1
{1}
Returns: 1
Submissions are judged against all 119 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LongMansionDiv2 with a public method long long minimalTime(int M, vector<int> t) · 119 test cases · 2 s / 256 MB per case