#3698. XWW的难题

XWW的难题

题目描述

XWW 是个影响力很大的人,他有很多的追随者。这些追随者都想要加入 XWW 教成为 XWW 的教徒。但是这并不容易,需要通过 XWW 的考核。

XWW 给你出了这么一个难题:XWW 给你一个 N×NN\times N 的正实数矩阵 AA,满足 XWW 性。

称一个 N×NN\times N 的矩阵满足 XWW 性当且仅当:

  1. A[N][N]=0A[N][N]=0
  2. 矩阵中每行的最后一个元素等于该行前 N1N-1 个数的和
  3. 矩阵中每列的最后一个元素等于该列前 N1N-1 个数的和

现在你要给 AA 中的数进行取整操作(可以是上取整或者下取整),使得最后的 AA 矩阵仍然满足 XWW 性。同时 XWW 还要求 AA 中的元素之和尽量大。

输入格式

第一行一个整数 N,N100N,N\le 100

接下来 NN 行每行包含 NN 个绝对值小于等于 10001000 的实数,最多一位小数。

输出格式

输出一行,即取整后 AA 矩阵的元素之和的最大值。无解输出 No

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0
129

数据规模与约定

1010 组数据,nn 的大小分别为 10,20,30...10010,20,30...100

提示

样例中取整后满足 XWW 性的和最大的矩阵为:

$$\begin{bmatrix} 3&7&8&18\\ 10&3&0&13\\ 4&1&7&12\\ 17&11&15&0\\ \end{bmatrix} $$