Processing math: 100%
编程题
                ### 问题描述

小齐是一位热爱摄影的农夫,他希望在自家牧场拍摄一张美丽的照片,用于装饰自己的房间。牧场可以看作是一个 N×N 的方格网格(可以想象成一个 N×N 的国际象棋棋盘)。在之前的照片中,小齐发现奶牛们聚集在一片区域,这次他希望奶牛们分散得更开一些。

为了达到这个目的,小齐提出了以下规则:

不能有两头奶牛放在同一个方格中。

每个 2×2 的子网格(总共有 (N1)×(N1) 个)必须包含恰好两头奶牛。

此外,小齐认为每头奶牛放置在方格 (i,j) 处时,照片的美感会增加 aij0aij1000)单位。

请计算小齐在这些规则下,能够得到的照片美感的最大值。

输入格式

第一行包含一个整数 N

接下来的 N 行,每行包含 N 个整数,第 j 个整数表示 aij

输出格式

输出一个整数,表示最大可能的照片美感。

样例输入

4
3 3 1 1
1 1 3 1
3 3 1 1
1 1 3 3

样例输出

22

评测数据规模

2N1000

查看答案
赣ICP备20007335号-2