Informatica Online Judge

  시노논과 피규어 [1297 / 0511]

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


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

[koistudy.net (32nd 박민수)]

Background

시노논은 아키바에서 시논의 피규어를 대량으로 판매하는 행사가 있다고 해서, 아키바로 건너갔다.

이 행사는 n*n 개의 피규어 상점들이 정사각형으로 배열되어 있으며,
상하좌우로 인접한 피규어 상점들끼리의 품질차는 1을 넘지 않고,
모든 피규어의 품질의 최대치는 100,000이라고 한다.

그러나 시노논은 시논의 피규어를 살 생각에 너무 기뻐서, 그만 계단에서 다리를 다치고 말았다.

그래서 시노논은 택시를 타고 피규어 상점에 가서 피규어를 구매하려고 하는데,
불행하게도 시노논은 여비가 단 한 곳을 왕복할 택시비 밖에 없어서 단 한 곳의 피규어 상점만을 들르려고 한다.

이 때 몇몇 상점의 피규어 품질이 주어질 때, 시노논이 살 수 있는 피규어의 품질의 가능한 최대치를 구하시오.

단 인접한 피규어 상점들끼리의 품질차가 1을 넘어야만 하는 상황이 발생한다면,
그것은 시노논이 꿈을 꾸고 있는 것이므로 “It’s a dream"을 출력하도록 한다.

Input

첫째 줄에 두 정수 한 변의 길이 n과 품질을 알고 있는 상점의 수 m이 주어지고
이후 m개 줄에 상점의 좌표 x,y와 피규어의 품질 p가 주어진다.

[입력값의 정의역]
2 ≤ n ≤ 3,000
1 ≤ m ≤ 100,000
1 ≤ x, y ≤ n
1 ≤ p ≤ 100,000

[SubTask Info]
#1 (30%): n<=20
#2 (30%): n<=200
#3 (40%): n<=3000

Output

시노논이 살 수 있는 피규어의 품질의 가능한 최대치를 출력하시오.

IO Example

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

출력1
6

설명

--4--
-2---
3---5
-43--
----5


43456
32345
33455
44345
55455

로 최대 6이다. 6이 나오는 배치는 여러 개가 있지만, 최대가 6이라는 건 변하지 않는다.
어떻게 해도 7이 나오게는 할 수 없다.

입력2
2 2
1 1 2
2 2 5

출력2
It’s a dream

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