소를 넓게 배치하기

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

요약

N x N 격자에 소를 배치하되 모든 2 x 2 부분격자가 정확히 소 두 마리를 포함하도록 하면서 칸 값의 합을 최대로 만든다. N은 1000까지이다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 수학, 행렬
정답자: 아직 제출이 없습니다

문제

농부 존은 목초지에서 풀을 뜯는 소들의 사진을 찍어 벽에 걸고 싶다. 목초지는 한 변의 길이가 $N$ 인 정사각형 격자로 나타낼 수 있고(즉 $N \times N$ 체스판), $2 \leq N \leq 1000$ 이다. 지난번에 찍은 사진에서는 소들이 목초지의 한쪽에 너무 몰려 있었다. 이번에는 소들이 목초지 전체에 적당히 흩어져 있게 하고 싶다. 그래서 농부 존은 다음 규칙을 지키기로 했다.

두 마리 이상의 소가 같은 칸에 있을 수 없다.
모든 $2 \times 2$ 부분 격자(총 $(N-1) \times (N-1)$ 개)에는 정확히 소가 2마리 있어야 한다.

예를 들어 다음 배치는 올바르다.

CCC
...
CCC

반면 다음 배치는 올바르지 않은데, 오른쪽 아래 모서리 칸을 포함하는 $2 \times 2$ 정사각형 영역에 소가 1마리밖에 없기 때문이다.

C.C
.C.
C..

다른 제한은 없다. 농부 존에게는 소가 무한히 있다고 가정해도 된다(지금까지의 경험에 비추어 보면 이 가정은 분명히 맞는 것 같다...).

농부 존은 어떤 칸에 소가 더 많이 들어가기를 바란다. 특히 소를 $(i, j)$ 번 칸에 놓으면 사진의 아름다움이 $a\_{ij}$ 만큼( $0 \leq a\_{ij} \leq 1000$ ) 증가한다고 생각한다.

올바른 배치에서 얻을 수 있는 아름다움의 최댓값을 구하라.

입력

첫째 줄에 $N$ 이 주어진다. 다음 $N$ 개 줄에 각각 $N$ 개의 정수가 주어진다. 위에서 $i$ 번째 줄의 $j$ 번째 정수가 $a\_{ij}$ 이다.

출력

완성된 사진의 아름다움의 최댓값을 정수 하나로 출력한다.

예제1

예제 1
입력
```
4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3
```
예상 출력
```
22
```