농부 존은 양질의 우유를 만들게 하기 위해 옥수수를 기르기로 하였다. 이를 위해 , 그가 찾을 수 있는 가장 평평한 땅에 옥수수 밭을 짓고자 한다.
그는 많은 돈을 들여 N*N ( 1 <= N <= 250 )의 정사각형 땅을 조사해서 각 정사각형의 땅을 고도( 0 <= 고도 <= 250 )별로 표시 한 후 찾고자 하는 부행렬의 최대/최소 차를 알고자 한다.
N (N*N) 크기 , B(B*B) 크기의 부 행렬 , K ( 1 <= K <= 100,000 )개의 질의
5 3 1 ----- N , B , K 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 ---- 1 행 2 열에서 3*3 크기의 부행렬에서 최대/최소 차처음의 5 는 5*5 를 , B 는 짓고자 하는 옥수수 밭의 크기 즉 3*3 부행렬 , k 는 질의 개수 즉 1 행 2 열에서 최대/최소의 차이
최대 6 , 최소 1 이므로 차는 5
질의의 첫수는 가장 위의 행이고 , 두번째 수는 가장 왼쪽의 열이다. 각 수의 범위는 1 .. N-B+1 이다.
입력 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
5 3 2 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... 1 행 2 열에서 3*3 의 최대/최소의 차이 3 1... 3 행 1 열에서 3*3 의 최대/최소의 차이
출처:USACO 2003 March Green