teleport1
You are given a board of size nxn. The bottom left corner has the coordinate (1, 1), and the top right one (n, n). The goal is to move from (1, 1) to (n, n) by moving only to the top or to the right. Some of the fields contain teleports. If a field (x,y) contains a teleport, then you can teleport to any field (u, t) for which: (u, t) != (x, y), u >= x, t >= y.
Note that you don't have to use the teleport. From a field (x, y) that contains a teleport you can move to (x+1, y) or (x, y+1), or decide to use the teleport..
Also, each field has a price for stepping on it. The price of the trip from (1,1) to (n,n) equals the sum of the prices of all the fields you have stepped on.
What is the price of the most expensive trip?
After that, the input contains an integer T - the number of teleports. Each of the following T lines contains 4 integers: x, y, u and t - there is a teleport from (x, y) to (u, t). A field can have at most one teleport.
7
5 1 -6 7 -9 1 2
1 -3 1 2 2 0 1
-4 2 -6 2 -4 1 1
-7 -4 2 -1 1 1 -2
2 -2 -1 -1 -4 -3 1
-3 -1 -1 1 -2 1 3
1 -2 -1 -3 2 -4 1
4
2 5 4 7
1 1 4 4
4 1 7 5
5 4 7 5Output:
9Explanation:
We are starting from the position (1, 1), and at that position we will use teleport to field (4, 4). After, we will move on the field (5, 4). On that field we could use teleport, but using teleport will lead as to worse solution, so we will continue moving on the field (6, 4). After, we will use fields (6, 5) -> (6, 6) -> (6, 7) -> (7, 7).
Sum of values on the used fields is 1 + (-1) + 2 + 2 + 2 + 0 + 1 + 2 = 9.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.