시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 507 | 194 | 148 | 43.023% |
N×N의 행렬이 있다(1 ≤ N ≤ 250). 행렬의 각 성분은 250보다 작거나 같은 음이 아닌 정수이다. 당신에게는 K(1 ≤ K ≤ 100,000)개의 질문이 주어진다. 각 질문은, 주어진 행렬의 B×B 크기의 부분행렬의 최댓값과 최솟값의 차이를 묻는 질문들이다(1 ≤ B ≤ N). 각 질문에 대해서, 부분행렬의 가장 왼쪽 위의 위치가 주어지며, 모든 질문들은 같은 B값을 갖는다. 질문에 답하는 프로그램을 작성하시오.
첫째 줄에는 세 정수 N, B, K가 주어진다. 다음 N개의 줄에는 행렬이 주어진다. 차례로 1행, 2행, …, N행이 된다. 각 줄에는 N개의 정수가 주어지며, 이는 차례로 1열의 성분, 2열의 성분, …, N열의 성분이 된다. 다음 K개의 줄에는 질문들이 주어진다. 각 질문들은 두 정수 i, j로 주어진다. i는 부분행렬의 가장 윗쪽의 행 번호이며, j는 부분행렬의 가장 왼쪽의 열 번호이다(1 ≤ i, j ≤ N-B+1)
K개의 줄에, 차례로 각 질문의 답변(부분행렬의 최댓값과 최솟값의 차이값)을 출력한다.
5 3 1 5 1 2 6 3 1 3 5 2 7 7 2 4 6 1 9 9 8 6 5 0 6 9 3 9 1 2
5