logo AlgoBeat OnlineJudge
登录 注册

#103698. [BZOJ 3698] XWW的难题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

XWW 给你出了这么一个难题:XWW 给你一个 的正实数矩阵 ,满足 XWW 性。

称一个 的矩阵满足 XWW 性当且仅当:

  1. 矩阵中每行的最后一个元素等于该行前 个数的和
  2. 矩阵中每列的最后一个元素等于该列前 个数的和

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

输入格式

第一行一个整数

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

129

数据范围与提示

组数据, 的大小分别为

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