레이팅 미적용설명
겨울 무림픽의 크로스컨트리 스키 코스는 고도로 이루어진 M x N 격자 (1 <= M,N <= 500)로 표현되며, 각 고도는 0 .. 1,000,000,000 범위이다.
이 격자의 일부 칸은 코스의 출발점으로 지정되어 있다. 주최 측은 각 출발점에 난이도 등급을 부여하려고 한다. 출발점 P의 난이도는, 소가 P에서 출발하여 두 칸 사이 고도 차이의 절댓값이 D 이하일 때에만 인접한 칸으로 이동할 수 있다고 할 때, 격자에서 총 T개 이상의 칸 (1 <= T <= MN)에 도달할 수 있게 되는 D의 가능한 최솟값이어야 한다. 두 칸은 한 칸이 다른 칸의 바로 북쪽, 남쪽, 동쪽, 서쪽에 있을 때 인접하다.
주최 측이 각 출발점의 난이도 등급을 계산하는 것을 도와주시오.
제약
입력 형식
첫째 줄에 정수 M, N, T가 주어진다.
둘째 줄부터 1+M번째 줄까지, 이 M개의 줄 각각에 N개의 정수 고도가 주어진다.
2+M번째 줄부터 1+2M번째 줄까지, 이 M개의 줄 각각에 0 또는 1인 값 N개가 주어지며, 1은 그 칸이 출발점임을 나타낸다.
출력 형식
모든 출발점의 난이도 등급의 합을 출력한다 (개별 난이도 등급은 32비트 정수 범위에 들어가지만, 이 합은 그렇지 않을 수 있음에 유의한다).
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
skilevel.in · 출력을 쓸 파일 skilevel.out예제 1
입력
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1출력
24설명
Output details: The difficulty rating of the upper-left starting point is 4, and the lower-right is 20.
문제 정보
태그