cinador   3년 전

문제

JOIG 왕국의 국토는 H행 W열의 직사각형 모양의 격자판으로 나타낼 수 있다. 위에서부터 i번째 행 (1 ≤ i ≤ H), 왼쪽으로부터 j번째 열 (1 ≤ j ≤ W) 에 위치한 칸을 (i,j) 라고 한다.

각 칸에는 높이에 해당하는 양의 정수가 부여된다. (i,j)의 높이는 Ai,j 이다.

JOIG 왕국은 왕국을 종단하는 운하를 건설하려고 한다. 운하의 건설은 다음과 같이 진행된다.

  •  1 ≤ k < W 를 만족하는 양의 정수 k를 정한다. 왼쪽에서부터 k번째 열과 k+1번째 열 사이에 왕국을 종단하는 운하를 건설한다. 즉, 운하에 의해 왕국의 국토가 1~k번째 열, k+1~W번째 열으로 분리된다.

임의의 칸에서 상하좌우로 인접하면서 높이가 같은 칸으로만 이동할 수 있을 때, 운하를 지나지 않으면서 이동을 반복해서 서로 방문할 수 있는 칸들의 집합을 평지라고 하자. 국토의 관리의 부담을 줄이기 위해 평지의 개수가 최소가 되게끔 운하를 건설하려고 한다.

JOIG 왕국의 지형의 정보가 주어졌을 때, 운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 구하여라 

ㅤ

입력

입력은 다음과 같은 형식을 갖는다.

preview

ㅤ

출력

 운하를 건설한 후 JOIG 왕국 내의 평지의 개수의 최솟값을 출력한다.

ㅤ

제한
  • H ≧ 1.
  • W ≧ 2.
  • H x W ≦ 500 000.
  • 1 ≦ Ai,j ≦ 109 (1 ≤ i ≤ H, 1 ≤ j ≤ W).
  • 모든 입력은 양의 정수이다.

ㅤ

예제 1 설명
preview

 k = 3 인 운하를 건설한다고 하면, JOIG 왕국에는 아래와 같은 4개의 평지가 존재한다.

  • (1, 1), (1, 2), (1, 3), (2, 3), (3, 2), (3, 3) 을 포함하는 평지
  • (2, 1), (2, 2), (3, 1), (4, 1), (4, 2), (4, 3) 을 포함하는 평지
  • (1, 4), (2, 4), (3, 4) 를 포함하는 평지
  • (4, 4) 를 포함하는 평지

JOIG 왕국 내의 평지의 개수가 3개 이하가 되게끔 운하를 건설할 수 없으므로 4를 출력한다.

ㅤ

예제 2 설명
preview

k = 1 인 운하를 건설하면 JOIG 왕국 내에는 8개의 평지가 존재한다. JOIG 왕국 내의 평지의 개수가 7개 이하가 되게끔 운하를 건설할 수 없으므로 8을 출력한다.

댓글을 작성하려면 로그인해야 합니다.