Informatica Online Judge

  네모난 도넛 [1423 / 058F]

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


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

[]

Background

경곽이는 이번에 새로 네모난 도넛을 개발했다.

이 도넛을 만들기 위해서 먼저 매우 큰 직사각형의 반죽을 만들었다.

그런데 양념이 제대로 섞이지 않아, 부분 부분 맛이 달라지게 되었다.

반죽의 각 영역에 기록된 값은 그 부분의 맛을 나타낸다. 값이 클수록 그 부분의 맛이 좋다는 의미이다.

다음은 10x10크기의 반죽의 예이다.



도넛은 다음과 같이 가운데가 빈 직사각형 모양으로 생겼다. (꼭 가운데에 빈 공간이 있어야 한다. 즉, 도넛은 최소 3x3이상의 크기를 가져야 한다.)

도넛은 도중에 끊어지지 않은 모양이어야 한다.



도넛의 맛은 잘라낸 부분의 소스의 양들의 합으로 정의된다. 위의 도넛의 맛은 3 + 5 + (-1) + (-2) + 4 + (-5) + 3 + 7 + 1 + 0 + (-6) + 4 + 3 + 2 + 4 + (-3) + 1 + (-2) = 18 이다.

경곽이는 다음과 같이 도넛을 만들고자 한다.


- 현재 만들어질 수 있는 도넛중에서 가장 맛있도록 도넛을 잘라내야 한다.

- 이런 방법으로 M번 반복하여 M개의 도넛을 잘라낸다.

- 만들어진 모든 도넛들은 도중에 끊어지지 않고 가운데가 빈 모양이어야 한다.


도넛이 도중에 끊어지지 않아야 한다는 말은 반죽에서 도넛들이 서로 겹치지 않아야 된다는 말과 같은 뜻이다.

예로 위의 반죽에서 4개의 도넛을 만들어 내는 문제를 생각해 보자.

첫번째로 만들 수 있는 가장 맛 좋은 도넛은 (3, 1)-(10, 9) 위치에서 잘라내면 만들 수 있다. 이 때의 도넛의 맛은 48이다.



반죽에서 도넛을 잘라내면 다음과 같은 모양이 된다.



이 반죽에서 가장 맛 좋은 도넛을 찾아보면 (7, 5)-(9, 7) 부분을 잘라내면 된다. 이 도넛의 맛은 6이다.



이런식으로 계속해서 도넛을 K개 만들면 된다.

반죽이 주어질 때 위 규칙에 맞도록 도넛을 만들 수 있는 프로그램을 작성하시오.

Input

반죽의 크기 N과 잘라낼 도넛의 개수 K이 공백으로 구분되어 입력된다.

다음 줄부터는 반죽이 NxN의 형태로 맛을 나타내닌 정수가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= K <= N <= 30
-100 <= 각 셀의 값 <= 100

Output

규칙에 맞도록 만드는 것이 불가능하면 0을 출력한다.

답이 있다면 도넛 하나 당 한줄 씩 그 정보를 출력한다.

각 도넛의 첫 번째 값은 도넛의 맛, 다음으로 도넛의 왼쪽위 좌표, 오른쪽 아래 좌표를 출력한다. (행, 열의 순)

입력되는 예시는 항상 답이 유일함을 보장한다.

IO Example

입력
10 4
1 -5 0 8 -1 -8 -3 5 4 -5
-4 10 -1 -6 -3 8 -4 4 -8 -8
-2 -4 -7 -6 7 2 -5 10 -9 -3
9 9 -7 -6 -6 -3 -8 -6 8 6
10 4 -2 2 -3 -9 -5 7 -4 -6
0 7 0 -7 -7 -7 -10 -5 -2 7
3 -10 0 -5 6 -2 3 -7 8 -3
9 -6 -8 -1 0 -1 -4 -3 -9 6
10 -4 -1 -7 -2 10 -5 -3 8 -7
0 5 -4 8 -3 0 -7 10 3 3

출력
48 3 1 10 9
6 7 5 9 7
2 4 2 6 4
-34 7 2 9 4

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