Informatica Online Judge

  고기잡이1 [1017 / 03F9]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 209   Total Tried : 260


The Champion of this Problem (C++) : gs16017 - ms / 337byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

우리나라 최고의 어부 경곽이가 이번에 네모네모 배 고기잡이 대회에 참가한다.

이 대회에는 3개의 라운드가 있는데, 첫 번째 라운드는 1차원형태로 표현될 수 있는 작은 연못에서 길쭉한 그물을 던져서 최대한 많은 고기를 잡는 것이 목적이다.

2라운드는 1차원 형태의 연못인데 크기가 매우 긴 연못이다.

3, 4라운드는 2차원 형태의 네모형태의 연못에서 2차원 그물을 던져서 물고기를 잡는 대회이다.

1라운드의 예를 들면 연못의 크기가 1*6이고 물고기의 위치와 가치가 다음과 같다고 하자.

1 0 2 0 4 3

여기서 그물의 크기는 1*3이라고 할 때

잡을 수 있는 방법은 (1 0 2), (0 2 0), (2 0 4), (0 4 3)의 4가지 방법이 있다.

이 중 가장 이득을 보는 방법은 마지막 방법 0 + 4 + 3 = 7이다. 따라서 주어진 경우의 최대 이득은 7이 된다. 경곽이는 최대한 가치있는 물고기를 잡아서 우승하고 싶어 한다.

연못의 폭과 높이값과 각 칸에 있는 물고기의 가치, 그물의 가로, 세로의 길이가 주어질 때, 잡을 수 있는 물고기의 최대이득을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 연못의 높이 H와 폭 W가 공백으로 구분되어 입력된다.
두 번째 줄에 그물의 높이 h와 폭 w가 공백으로 구분되어 입력된다.
세 번째 줄부터 H줄에 걸쳐서 각 줄에 W개씩 공백으로 구분되어 물고기의 가치가 주어진다. 각 물고기의 가치는 7이하의 자연수이다. 0일 경우에는 물고기가 없다는 의미이다.

[입력값의 정의역]
1 <= W, H
W*H <= 3,000,000
H <= 3,000
0 <= w <= W
0 <= h <= H

[Sub-Task Info]
#1 : H = 1, W <= 100을 만족한다.
#2 : H = 1, W <= 100,000을 만족한다.
#3, #4 : 추가적인 제한 조건은 없다.

Output

첫 번째 줄에 잡을 수 있는 물고기의 최대 이익을 출력한다.

IO Example

입력
1 6
1 3
1 0 2 0 4 3

출력
7

입력2
2 6
1 3
1 0 2 0 4 3
3 4 0 2 0 1

출력2
7

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