| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB | 194 | 43 | 35 | 50.000% |
재민이의 생일을 맞아 $N$명의 친구들이 생일 파티에 초대되었습니다. 재민이는 친구들을 위해서 직사각형 모양의 케이크를 하나 준비했습니다.
재민이가 준비한 케이크는 $H\times W$ 크기의 격자 모양으로 나뉘어, 총 $HW$개의 조각들로 이루어져 있습니다. 각 조각은 단맛의 정도에 따라 1ドル$ 이상 10ドル^{9}$ 이하의 정수 값이 주어집니다. 이 값이 클 수록 더 달콤한 조각임을 의미합니다. $i$행 $j$열에 위치한 조각 $(i,j)$는 $S_{ij}$ 만큼의 단맛을 가집니다.
재민이는 친구들이 오기 전에, 친구들에게 나누어 줄 조각들을 다음 조건을 만족하도록 골라 놓으려고 합니다.
어떤 조각들이 직사각형 영역을 이룬다는 것은, 다음 조건을 만족하는 4ドル$개의 정수 $s_1,e_1,s_2,e_2$가 존재함을 의미합니다.
재민이는 친구들이 어느 정도의 단맛을 좋아하는 지 모르기 때문에, 선택된 $N$개의 조각들 중 가장 단맛이 큰 조각과 가장 단맛이 작은 조각의 단맛의 차이를 최대화하려고 합니다. 재민이를 도와 어떤 조각들을 선택해야 하는지 구해봅시다!
첫째 줄에 케이크의 크기를 나타내는 두 정수 $H,ドル $W$와 친구들의 수 $N$이 공백으로 구분되어 주어집니다. (1ドル\le H,W\le 500,円 000$; $HW\le 500,円 000$; 1ドル\le N\le HW$)
둘째 줄부터 $H$개의 줄에 걸쳐, 각 조각의 단맛을 나타내는 정수 $S_{i1},ドル $\cdots,ドル $S_{iW}$가 공백으로 구분되어 주어집니다. (1ドル\le S_{ij}\le 10^{9}$)
조건을 만족하도록 케이크를 자르는 것이 불가능한 경우 $-1$을 출력합니다.
케이크를 자르는 것이 가능한 경우, 단맛의 차이의 최댓값을 출력합니다.
3 5 6 6 5 4 8 7 2 4 4 5 6 3 1 3 5 2
6
2 6 9 3 6 4 3 5 8 2 1 5 1 5 9
-1
2 3 1 17 13 84 81 22 47
0