| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 52 | 31 | 25 | 54.348% |
유토는 X 칠하기 게임을 하려고 한다. X 칠하기 게임은 $N\times N$ 격자의 칸을 칠하는 게임이다. 처음에 각 칸은 비어 있으며, 플레이어는 적당히 칸들을 골라 색칠할 수 있다. 이때, 색칠된 두 칸이 서로 인접할 수 없다.
게임의 점수는 다음과 같이 결정된다.
여기서, X 모양은 다음 그림과 같은 모양을 의미한다. 즉, $(i-1,j-1)$, $(i-1,j+1)$, $(i,j)$, $(i+1,j-1)$, $(i+1,j+1)$ 이 모두 칠해진 $(i,j)$ 쌍 하나마다 $K$점을 얻는다.
이때 유토가 받을 수 있는 최대 점수를 구해보자!
첫 번째 줄에 격자판의 크기를 의미하는 $N$, $K$가 공백으로 구분되어 주어진다.
이후 $N$개의 줄에 걸쳐, 각 칸을 색칠하면 얻을 수 있는 점수 $A_{ij}$ 가 주어진다.
유토가 받을 수 있는 최대 점수를 출력한다.
3 1 10 -5 7 -2 -2 8 -2 -6 6
23
3 4 10 6 7 -2 -2 8 -1 -6 6
24
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final G번