Informatica Online Judge

  풍력 발전기 [1038 / 040E]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 10   Total Tried : 34


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

최근에 친환경에너지로 태양열, 풍력, 수력 등의 발전시설이 인기가 많다.

우리나라 최고의 과학자인 경곽이는 특히 풍력 발전에 관심이 많다.



따라서 경곽이는 우리나라에 풍력발전기를 설치하기 위한 장소를 조사하고 있다.

우리나라의 수력발전기를 설치하고자 하는 지역의 지도가 주어진다.

그 지도는 N*M(N행, M열)의 구역으로 이루어져 있으며, 각 구역에는 기압이 주어진다.

풍력발전의 효율을 높이기 위해서는 강한 바람이 필요하다.

바람이 강하려면 그 지역의 기압의 차가 커야한다.

경곽이가 설치하려는 발전기를 설치할 영역의 크기는 세로가 h, 가로가 w이다.

발전기를 설치하고자 하는 지역 중 h*w영역을 골라서 발전기를 설치하려고 한다.

각 h*w지역의 발전효율은 그 영역에서 가장 기압이 센 영역과 기압이 가장 약한 영역의 차로 결정한다.

즉, 다음과 같은 식으로 발전효율을 결정할 수 있다.

발전효율 = max(y,x,h,w) - min(y,x,h,w)

(단, min(a,b,c,d)는 영역(a,b)~(a+h-1,b+w-1)영역 중 최소기압을 의미하고,
max(a,b,c,d)는 영역(a,b)~(a+h-1,b+w-1)영역 중 최대기압을 의미한다.)

발전소를 설치할 N*M영역의 기압정보와 발전기의 크기 h, w가 주어질 때, 가장 높은 효율을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 영역의 크기 N과 M, 발전기 설치 영역의 세로의 크기 h, 가로의 크기 w가 공백으로 구분되어 입력된다.
두 번째 줄부터 N줄에 걸쳐서 각 줄에 M개의 기압정보가 주어진다.

[입력값의 정의역]
1 <= N, M
N*M <= 1,000,000
max(N, M) <= 1,000
1 <= w, h <= N, M
0 <= 기압정보 <= 10,000

[Sub Task Info]
#1 : N = 1; M <= 100
#2 : N = 5; M <= 1,000; 3 <= h <= 5
#3 ~ #4 : N = M, 추가제약조건은 없다.

Output

첫 번째 줄에 가장 효율이 좋은 영역의 효율을 출력한다.

IO Example

입력1
1 10 1 5
0 1 2 5 2 3 7 4 4 0

출력1
7

* 설명
5번째~10번째 까지의 영역의 최대기압은 7, 최소기압은 0이므로 7-0 = 7이 최적이다.

입력2
5 5 2 2
5 8 9 2 0
0 1 11 5 3
2 3 1 2 3
1 2 2 2 5
5 2 0 2 5

출력2
10

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]