ID: 788

传统题

1000ms

256MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

Vllilac_Peng

题目背景

你说的对，但是《原神》是由上海米哈游网络科技股份有限公司制作发行的一款开放世界冒险游戏。游戏发生在一个被称作“提瓦特大陆”的幻想世界，在这里，被神选中的人将被授予“神之眼”，导引元素之力。玩家将扮演一位名为“旅行者”的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人——同时，逐步发掘“原神”的真相。

I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
I want to TLE
is
in for range
max
import

题目描述

芙宁娜的生日是 10 月 13 日。在这天，卸任后的她成功研发出了一款蛋糕：超级矩阵蛋糕！

「超级矩阵蛋糕」可以被视为一个 $n$ 行 $m$ 列、每个单元格里的元素均为正整数的矩阵。勤奋的芙芙，在三个动物朋友的帮助下，成功烤了一堆不同规格的超级矩阵蛋糕。

为了判断蛋糕是否足够美丽，芙芙制定了如下打分规则。每次打分时，会对一个蛋糕打出一个二元组分数 $(A,B)$ 。

分数 $A$ 表示的是蛋糕中单调不降行的数量。具体来说，如果该行中的值从左到右是 $v_1,v_2...v_m$ ，则如果 $v_1 \le v_2 \le ... \le v_m$ ，则该行是单调不降的。
分数 $B$ 表示的是蛋糕中常量列的数量。如果该列中的值都相同，则该列是常量列。

而伟力无边的时间之魔神「派蒙（Paimon）」对蛋糕进行了偷吃！这使得蛋糕一些格子上的值缺失了。身为派蒙仆人的你，现在需要对矩阵上的缺失值进行填充。注意，只能填充正整数哦~

因此，被整个枫丹寄以厚望的你，现在需要填充该矩阵的缺失值，以创建可能的最佳矩阵得分。

矩阵“更好”的定义：

设有一个得分为 $(A, B)$ 的矩阵，另一个矩阵得分为 $(A',B')$ 。则若第一个矩阵更好，当且仅当满足以下条件之一：

$A \gt A'$ 。
$A = A'$ 且 $B \gt B'$ 。

输入格式

第 $1$ 行共两个正整数 $n$ ， $m$ ，描述蛋糕的尺寸。

第 $2\sim n + 1$ 行，每行包含 $m$ 个整数用于描述矩阵。矩阵中的每个值要么是正整数，要么是零。某个元素为0 则代表该位置存在缺失的值，需要填充。

输出格式

在单独一行上输出两个整数 $A$ 和 $B$ ，表示可以创建的最佳矩阵的得分 $(A,B)$ 。

样例

样例 #1

样例输入 #1

样例输出 #1

2 3

样例 #2

样例输入 #2

2 3
1 0 2
3 0 4

样例输出 #2

2 0

样例 #3

样例输入 #3

2 4
2 4 0 1
2 0 3 1

样例输出 #3

0 4

样例 #4

见附加测试用例 big_matrix100.in/.out。

big_matrix100.in

big_matrix100.out

样例 #5

见附加测试用例 big_matrix.in/.out。

big_matrix.in

big_matrix.out

提示

对于样例 1，可以将矩阵补充为

2 3 3 6 8
1 3 1 6 8
1 3 6 6 8

使得第 $1,3$ 行是单调不降行，第 $2,4,5$ 列为常量列， $A=2,B=3$ 。

数据范围

对于前 $20\%$ 的数据，满足 $1\le n,m \le 4$ 。

对于前 $40\%$ 的数据，满足 $1\le n,m \le 100$ 。

对于另外 $20\%$ 的数据，满足 $v_{i,j} \neq 0$ 。

对于全部数据 $1 \le n,m \le 10^5,1\le n\times m \le 10^6,0 \le v_{i,j} \le 10^6$ 。

其中， $v_{i,j}$ 为输入的矩阵第 $i$ 行第 $j$ 列的数字。

#xhz. 你说的对

你说的对