레이팅 미적용농부 존은 벽에 걸어 놓기 위해 목초지에서 풀을 뜯는 소들의 사진을 찍고 싶어 한다. 목초지는 정사각형 칸들로 이루어진 \(N \times 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\))만큼 증가한다고 믿는다.
유효한 소 배치의 총 아름다움의 최댓값을 구하시오.
문제 제공: Hankai Zhang, Danny Mittal
배점
- 테스트 케이스 2-4는 \(N \le 4\)를 만족한다.
- 테스트 케이스 5-10은 \(N\le 10\)을 만족한다.
- 테스트 케이스 11-20은 \(N \le 1000\)을 만족한다.
문제 제공: Hankai Zhang, Danny Mittal
첫째 줄에 \(N\)이 주어진다. 다음 \(N\)개의 줄에 각각 \(N\)개의 정수가 주어진다. 위에서 \(i\)번째 줄의 \(j\)번째 정수가 \(a_{ij}\)의 값이다.
결과 사진의 아름다움의 최댓값을 정수 하나로 출력한다.
4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 322In this sample, the maximum beauty can be achieved with the following placement:
CC..
..CC
CC..
..CC
The beauty of this placement is \(3 + 3 + 3 + 1 + 3 + 3 + 3 + 3 = 22\).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > January > Silver