페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8362
서브태스크

주요 도로 1s 1024MB

문제

정올 도시는 동서 방향으로 평행하게 무한히 뻗어 있는 H개의 도로와 남북 방향으로 평행하게 무한히 뻗어 있는 W개의 도로로 이루어진 격자 형태의 도로망을 가지고 있다. 도로와 도로 사이의 간격은 1이다. 정올 도시에서는 이 H+W개의 도로 중에서 동서 방향 도로 1개와 남북 방향 도로 1개, 총 2개의 도로를 주요 도로(간선도로)로 선택하기로 하였다.

북쪽에서 i번째 (1≦i≦H) 도로와 서쪽에서 j번째 (1≦j≦W) 도로가 만나는 교차점을 교차점 (i,j)라고 한다. 교차점 (i,j)와 북쪽에서 m번째 (1≦m≦H) 도로 사이의 거리는 |i-m|이며, 교차점 (i,j)와 서쪽에서 n번째 (1≦n≦W) 도로 사이의 거리는 |j-n|이다. 또한, 교차점 (i,j) 주변에는 A_{(i,j)}명의 주민이 거주하고 있다.

동서 방향 도로 1개와 남북 방향 도로 1개, 총 2개의 주요 도로를 선택했을 때, 정올 도시의 모든 주민이 주요 도로까지 이동해야 하는 거리의 총합의 최솟값을 구하여라.

다시 요약하자면, 정올 도시는 H개의 동서 방향 도로와 W개의 남북 방향 도로로 구성된 격자 형태의 도로망을 가지고 있고, 각 교차점에는 A_{(i,j)}명의 주민이 거주하며, 두 주요 도로(동서 방향 1개, 남북 방향 1개)를 선택할 때, 각 주민이 거주하는 교차점에서 주요 도로까지 이동해야 하는 거리가 발생한다. 문제는 모든 주민의 이동 거리 총합이 최소가 되도록 주요 도로를 선택하는 것이다.


입력

입력은 다음 형식으로 표준 입력을 통해 주어진다.

H W

A_({1,1)} A_({1,2)} ... A_({1,W)}

...

A_({H,1)} A_({H,2)} ... A_({H,W)}

[제한]
2 ≦ H ≦ 25
2 ≦ W ≦ 25
0 ≦ A_{(i,j)} ≦ 100 (1 ≦ i ≦ H, 1 ≦ j ≦ W)


출력

정올 도시의 모든 주민이 해당 교차점에서 가장 가까운 주요 도로까지 이동하는 거리의 총합의 최솟값을 출력하라.


부분문제

번호 점수 조건
#130점

모든 A_{(i,j)} = 1 (1 ≦ i ≦ H, 1 ≦ j ≦ W)

#270점

추가 제약 조건 없음


예제 #1

3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
8

예를 들어, 북쪽에서 2번째 도로와 서쪽에서 1번째 도로를 주요 도로로 선택하면 된다.


예제 #2

5 5
1 2 3 1 5
1 22 11 44 3
1 33 41 53 2
4 92 35 23 1
4 2 6 3 5
164

만약 북쪽에서 1번째 도로와 서쪽에서 1번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 582가 된다.

만약 북쪽에서 2번째 도로와 서쪽에서 2번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 225가 된다.

만약 북쪽에서 3번째 도로와 서쪽에서 2번째 도로를 주요 도로로 선택하면 이동하는 거리의 총 합은 164가 된다.



출처

JOI 2018 예선
로그인해야 코드를 작성할 수 있어요.