정올 도시는 동서 방향으로 평행하게 무한히 뻗어 있는 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개)를 선택할 때, 각 주민이 거주하는 교차점에서 주요 도로까지 이동해야 하는 거리가 발생한다. 문제는 모든 주민의 이동 거리 총합이 최소가 되도록 주요 도로를 선택하는 것이다.

#8362 upload 3 done 3 how_to_reg 3 call_split Subtask

주요 도로 timer 1s memory 1024MB

#8362
Subtask

주요 도로 1s 1024MB