시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 249 | 111 | 85 | 51.829% |
화학이 싫어서 지구과학을 공부한 선영이가 기상예측을 하는 일을 맡게 되었다.
선영이가 기상예측을 해야 되는 지역은 N×M짜리 격자판이고 각각의 칸마다 기상예측을 하는데 걸리는 시간이 있다.
이때 선영이는 이 격자판을 적당히 나눠서 각각의 구간의 작업을 동시에 할 수 있는데 그러므로 나누어진 구간 중 작업시간의 합이 최대인 곳을 최소화 한다면 선영이의 작업량이 최소가 될 것이다. 이때 나누는 기준은 주어진 개수의 가로선과 세로선을 이용해서 나누면 된다.
가로로 나눌 수 있는 선의 개수가 주어지고 세로 역시 주어진다고 할 때 나누어진 구간의 합의 최대를 최소로 하는 나누는 방법을 구하라.
첫줄에는 n, m, r, s(1 ≤ r < n ≤ 18, 1 ≤ s < m ≤ 18) 가 주어지는데 n, m은 지역의 가로, 세로크기, r, s는 가로로 나누는 수, 세로로 나누는 수를 의미한다. 그 뒤로는 각각의 칸을 예측하는데 걸리는 시간이 주어진다. 시간은 2,000,000이하의 음이 아닌 정수이다.
선영이가 결과를 구하는데 걸리는 최소의 시간을 출력한다.
7 8 2 1 0 0 2 6 1 1 0 0 1 4 4 4 4 4 3 0 2 4 4 4 4 4 3 0 1 4 4 4 8 4 4 0 0 3 4 4 4 4 4 3 0 1 1 3 4 4 3 0 0 0 0 1 2 1 2 0
31