Informatica Online Judge

  주거지 관리 [0957 / 03BD]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 8   Total Tried : 16


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

[Jihak Yoon (koistudy.net)]

Background

일정한 직업이 없던 경곽이는 열심히 공부를 하여 주거지를 관리하는 공무원이 되었다.

주거지는 집을 N*N으로 나열한 2차원 격자판으로 나타내어지고, 경곽이는 각 집마다 사는 사람 수를 알고 있다.

어느 날 경곽이는 인접한 K개의 집을 연결하여 관리해야 할 필요성이 생겼다. 여기서 인접한다는 것은 상하좌우로 연결되어 있다는 것이다. 대각선은 포함되지 않는다.

자세한 것은 국가의 일이라서 말할 수 없지만, 경곽이는 이 K개의 집들 중 가장 적은 사람이 사는 곳의 사람 수를 최대화해야 한다.

그러나 국가에서 경곽이에게 요구한 K가 한 개가 아니라 여러 개여서, 당신에게 도움을 요청했다.

각 집마다 사는 사람 수와 경곽이에게 요구한 K들이 주어질 때, 각 K에 대하여 가장 적은 사람이 사는 곳의 사람 수의 최대 수를 구하여라.

Input

첫 줄에 N이 주어진다. ( 1<=N<=300 )
다음 N줄에 N개의 수가 주어진다. 이는 각 집마다 사는 사람 수를 의미한다. 이 값은 1,000,000,000 이하의 자연수이다.

바로 다음 줄에 M이 주어진다. 이는 K들의 갯수이다. ( 1<=M<=100,000 )
다음 줄에 공백을 사이에 두고 M개의 수가 주어진다. 이는 K들을 의미한다. ( 1<=K<=N*N )

Output

첫 줄에 M개의 수를 출력한다. 이는 각 K들에 대한 답이다.

IO Example

입력1

2
1 2
3 4
4
1 2 3 4

출력1

4 3 2 1

입력2

3
5 9 10
4 8 2
11 1 3
9
1 2 3 4 5 6 7 8 9

출력2

11 9 8 5 4 4 2 2 1

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