Informatica Online Judge

  유난히 돋보이는 뚝배기 [2099 / 0833]

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


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

[koistudy.net (unkonwn)]
Writer ID : [gs16053]

Background

cube는 재미를 위해 경곽인들을 소집하여 가로 $w$명, 세로 $h$명이 되도록 일렬로 세웠다.
cube는 이들 모두의 키를 알고 있는데, 키 차이 때문에 "유난히 돋보이는 뚝배기"들이 생긴다. "유난히 돋보이는 뚝배기"는 다음과 같이 정의된다.

1. "유난히 돋보이는 뚝배기"는 같은 키를 가지는 한 명의 학생 혹은 인접한 학생들의 뚝배기들을 의미한다. 상하좌우 및 대각선으로 붙어있는 것을 "인접한다"고 부른다.
2. "유난히 돋보이는 뚝배기"를 가진 학생은 인접한 학생보다 키가 크거나 같다.
3. "유난히 돋보이는 뚝배기"를 가진 학생은 cube보다 키가 크다.

cube의 키는 $a$cm이며, cube는 $a$cm보다 작은 키를 가진 학생들에게 "유난히 돋보이는 뚝배기"를 깰 수 있는 기회를 주었다. 한 학생 당 때리는 횟수와 맞는 횟수에는 제한이 없다고 할 때, 뚝배기를 깨는 총 횟수가 최대가 되려면 $a$의 값은 얼마여야 하는가?

Input

첫번째 줄에 $h$, $w$가 주어진다.
이후 $h$개의 줄마다 $w$개의 자연수가 주어진다.

[입력값의 정의역]
$1≤w≤2000$
$1≤h≤2000$
입력되는 각 학생의 키는 140 이상, 200 이하의 자연수

Output

뚝배기를 깨는 총 횟수를 최대로 만드는 자연수 $a$의 값을 모두 공백을 사이에 두고 출력한다. $a$의 값에 관계없이 뚝배기를 깨는 것이 불가능할 경우 -1을 출력한다.

IO Example

<입력1>
4 4
161 162 163 162
160 161 160 160
160 159 165 165
163 160 160 165

<출력1>
162

설명1
$a≤159$이면 기준 미달인 학생이 없으므로 뚝배기를 깰 수 없다.
$a=160$이면 기준 미달인 학생이 1명 존재하고 "유난히 돋보이는 뚝배기"는 5개 있으므로 뚝배기는 총 1×5=5번 깨진다.
$a=161$이면 기준 미달인 학생이 7명 존재하고 "유난히 돋보이는 뚝배기"는 5개 있으므로 뚝배기는 총 7×5=35번 깨진다.
$a=162$이면 기준 미달인 학생이 9명 존재하고 "유난히 돋보이는 뚝배기"는 5개 있으므로 뚝배기는 총 9×5=45번 깨진다.
$a=163$이면 기준 미달인 학생이 11명 존재하고 "유난히 돋보이는 뚝배기"는 3개 있으므로 뚝배기는 총 11×3=33번 깨진다.
$a=164$이면 기준 미달인 학생이 13명 존재하고 "유난히 돋보이는 뚝배기"는 3개 있으므로 뚝배기는 총 13×3=39번 깨진다.
$a≥165$이면 "유난히 돋보이는 뚝배기"가 없으므로 뚝배기를 깰 수 없다.


<입력2>
4 4
161 161 165 161
160 161 160 160
160 159 166 166
165 160 160 166

<출력2>
162 163 164

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