가장 좋은 풀밭

면접 대비

시간 제한1초메모리 제한128 MB

요약
우유 생산량 격자에서 합이 가장 큰 3x3 부분 격자를 찾아 그 합과 왼쪽 위 모서리 좌표를 출력하고, 동점이면 행이 작은 것, 그다음 열이 작은 것을 고른다.
난이도

쉬움10점 중 3점

유형
배열, 누적 합, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

베시(Bessie)는 목장 어딘가에 세상에서 가장 좋은 특별한 풀이 자라는 자리가 있다고 믿는다. 그 풀을 먹은 소는 우유를 더 많이 생산한다.

목장은 NRNR개의 행과 NCNC개의 열로 이루어진, 빈칸 없이 가득 찬 직사각형 격자이며 각 칸마다 소가 한 마리씩 있다. 여기서 3≤NR≤1003 \le NR \le 100, 3≤NC≤1003 \le NC \le 100이다. 칸 (r,c)(r, c)에 있는 소의 우유 생산량을 PrcP_{rc}라 하며 1≤Prc≤1001 \le P_{rc} \le 100이다.

베시는 우유 생산량의 합이 가장 큰 3×33 \times 3 크기의 정사각형 구역을 찾아 특별한 풀의 위치를 알아내려 한다.

격자 안의 모든 3×33 \times 3 정사각형 중에서 아홉 칸의 생산량 합이 가장 큰 것을 찾아, 그 합과 그 정사각형의 왼쪽 위 칸의 위치(행 번호를 먼저, 그다음 열 번호)를 출력하여라. 행과 열 번호는 모두 1부터 시작한다.

합이 같은 3×33 \times 3 정사각형이 여러 개라면 행 번호가 가장 작은 것을 출력한다. 그래도 여러 개라면 그중 열 번호가 가장 작은 것을 출력한다.

입력

  • 첫째 줄: 두 정수 NRNR과 NCNC가 공백으로 구분되어 주어진다.
  • 둘째 줄부터 NR+1NR+1째 줄까지: r+1r+1째 줄에는 격자의 rr번째 행을 나타내는 NCNC개의 정수가 공백으로 구분되어 주어진다.

출력

  • 첫째 줄: 3×33 \times 3 정사각형에서 가능한 가장 큰 합을 나타내는 정수 하나.
  • 둘째 줄: 가장 좋은 3×33 \times 3 정사각형의 왼쪽 위 칸의 행 번호와 열 번호를 공백으로 구분하여 출력한다.

예제1

  1. 예제 1

    입력
    6 5
5 6 7 4 6
7 7 8 6 5
9 9 8 3 5
8 8 7 6 4
4 5 2 4 5
3 4 2 3 4
    예상 출력
    71
2 1