Informatica Online Judge

  신앙군주 [2128 / 0850]

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


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

[24th 김한빈]
Writer ID : [gs16023]

Background

세계는 n*m짜리 격자로 이루어져 있고, 각 격자마다 도시국가가 하나씩 있으며, 각 도시국가마다 ‘경기과학고등학교’의 신자가 a[i][j]명씩 있다. 세계는 다양하기 때문에 각 a[i][j]는 모두 다르다

변방의 군주 경곽이가 다스리는 (1,1)의 도시국가 GSHS국은 과격종교 ‘경기과학고등학교’를 국교로 삼는 국가이다.

이 종교는 많은 사람들에게 종교를 전파하는 것을 최우선으로 치기 때문에, GSHS국은 나라가 안정된 2년째부터 1년에 한번씩 도시국가 한 곳을 병합한다.

경곽이는 매우 독실한 신자이기 때문에, 병합을 할 곳을 고를 때는 GSHS국의 영토와 붙어 있는 도시국가들 중 가장 신자들이 적은 곳을 골라 병합한다.
GSHS국과 상하좌우로 인접한 칸들 중 가장 작은 수의 신자를 가지고 있는 도시국가와 병합을 하면, 그 도시국가의 신자의 수만큼 ‘경기과학고등학교’의 신자가 늘어난다.

다만 ‘경기과학고등학교’에 적대적이어서 음수의 값을 가진 도시국가들이 있는데, 이런 나라와 영토가 인접하게 되면 경곽이는 전쟁을 일으켜 그 도시를 쓸어버리고, 그곳의 신자를 10명으로 만들어 버린다.

‘경기과학고등학교’의 신자가 10명 증가하는 것이다. 물론 이 때도 경곽이는 가장 괘씸한 국가를 혼내주기 위해 가장 적대적인 곳과 전쟁을 한다.

당신은 경곽이의 신하이다. 경곽이는 t년 후 ‘경기과학고등학교’를 믿는 신자가 몇 명일지 궁금해 하므로, 당신은 그 수를 정확히 구해 알려줘야 한다.

경곽이는 매우 난폭한 폭군이므로, 제대로 대답하지 못한다면 끔찍한 일이 발생할 것이다.

T년 후 ‘경기과학고등학교’의 신자가 몇 명일지 구해보자. 단, 경곽이는 자신이 절대 전쟁에서 패배할 것이라 생각하지 않기 때문에, 모든 전쟁/병합은 성공한다 가정한다.

Input

첫 줄에 전체 지도의 크기 n, m과 시간 t가 주어진다.(1<=n, m, t<=100)

이후 n줄에 걸쳐 m개의 수 a[i][j]가 입력되며, 이는 각각 도시국가들의 신자의 수를 뜻한다.

A[i][j]는 -10000에서 10000 사이에 존재한다.

Output

첫 줄에 t년 후 ‘경기과학고등학교’의 신자의 수를 출력한다.

IO Example

입력1
3 4 5
1 2 -3 10
41 5 6 15
7 8 9 43

출력1
24

입력2
4 7 7
5 4 7 12 76 25 13
1 6 23 14 34 98 21
3 43 17 54 16 32 35
2 75 33 11 41 10 30

출력2
28

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