시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 72 | 24 | 23 | 58.974% |
Justin and Fred are taking a road trip, traveling from West to East across their state. They have a few Road Trip Rules:
Because Justin and Fred are traveling Eastward, a “pass” is any location with strictly lower elevations to its East and West and strictly higher elevations to its North and South. Consider the elevation map shown in Figure E.1. Undrivable locations (either due to water or stubborn insistence on staying in-state) are shown in black, while passes are shown as gray. Locations adjacent to the border or to undrivable locations are not eligible for considerations as passes.
Figure E.1: A sample elevation map
The input begins with three integers r c n representing the number of rows and columns in the representation of the state’s topography (3 ≤ r, c ≤ 500) and the exact number of passes to be crossed (0 ≤ n ≤ 10). The next r lines each contain c elevation entries. Undrivable locations are represented by −1, and all other elevations are between 0 and 1 000. There is guaranteed to be at least one drivable location on both the Eastern and Western borders.
Output the sum of the elevations along the optimal path which satisfies the Road Trip Rules. If no such path exists, output impossible.
5 7 2 -1 -1 2 5 4 3 1 3 4 1 4 1 2 1 3 4 5 5 3 4 5 2 3 2 1 2 3 2 -1 5 4 1 4 4 2
14
4 3 1 3 4 5 2 4 2 1 5 4 1 1 1
impossible