루미 알고리즘

#1657실버Long Staircases

PO 2026 학교 예선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

It is said that high up in the Alps live C sisters, each of whom has her own favorite number f. Every sister has therefore built a house f units of height above the surface of the water. The houses are built on a grid of size R × C, such that the bottom left cell is (0,0) and the top right cell is (C-1,R-1). The first sister has built her house at (0,0), the second at (1,0), and so on, so that the last sister has built her house at (C-1,0). In other words, the houses are built along the bottom row of the grid.

With the houses located so high up, it becomes difficult to get up and down. Every sister has therefore built a staircase from her house up through the R-1 rows above it, where the height decreases by 1 for every step. So for every cell that is not on the bottom row, there is a cell below it whose height is 1 greater. For example, if a sister's house is at (2,0) and has height 10, she builds a step at (2,1) with height 9, a step at (2,2) with height 8, and so on.

You are currently on this grid. More precisely, you are at the coordinates (s_x, s_y) and want to get to (g_x, g_y). You can move to cells that are adjacent either up, left, down or right. Going right or left is never a problem, even if there may be large differences in height. Naturally, you cannot move to a coordinate outside the grid.

High altitudes are quite strenuous, so your goal is to minimize the time you spend at high altitude. More precisely, if your walk from (s_x, s_y) to (g_x, g_y) visits a certain set of cells, we define the strain of the walk as the sum of the heights of all the cells you visit. If you walk optimally, what is the smallest possible strain?

(그림은 원문 저장소에서 볼 수 있습니다)

The picture shows what the grid looks like in sample 1. The bottom row contains the sisters' houses. The start and the goal are also marked, along with the least straining walk between them.

Input

The first line of input contains R and C (1 ≤ R ≤ 10^9, 1 ≤ C ≤ 10), the dimensions of the grid.

The second line contains C integers f_1, …, f_C (R-1 ≤ f_i ≤ 10^9), the height at which each sister's house is located. f_1 is the height of the house at (0,0), f_2 of the house at (1,0), and so on. Note that the heights f_i are chosen so that the remaining heights in the grid are not negative.

The third line contains the integers s_x and s_y (0 ≤ s_x < C, 0 ≤ s_y < R), the coordinate where you start.

The fourth line contains the integers g_x and g_y (0 ≤ g_x < C, 0 ≤ g_y < R), the coordinate you want to get to.

Output

Print an integer: the strain of the least straining walk from the start to the coordinate you want to get to. Note: the answer does not necessarily fit in a 32-bit integer.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
120C = 2
240R ≤ 10000
340No additional constraints.

Explanation of Sample 1

Sample 1 is the grid shown in the picture above. The least straining walk goes right, right, up, up, up, up, left, left. The strain is 15+12+5+4+3+2+1+8+11=61.

예제

예제 1

입력
5 3
15 12 5
0 0
0 4
출력
61

예제 2

입력
5 3
5 20 25
1 4
2 0
출력
76

예제 3

입력
100000 6
218849 99999 100019 100003 100000 264319
1 8493
5 99998
출력
4186884119

출처 표기

출처: Programmeringsolympiaden 2026년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.