#P3358. [Usaco2004 Jan]洪水

[Usaco2004 Jan]洪水

[USACO 2004 Jan] 洪水

题目描述

农场面临洪水威胁。约翰想知道水会涨到多高,以便把奶牛转移到安全的地方。

农场由 mm 行 nn 列的单位方格组成。格子 (i,j)(i,j) 的地面海拔为 hi,jh_{i,j},表示该格从海平面起堆叠了 hi,jh_{i,j} 层单位体积的陆地。体积为 vv 的水会先填到海拔最低的格子,不受格子之间的位置关系影响。求最终的水面高度,以及所有被完全淹没的格子中陆地的总体积。当格子的地面与水面等高时,这个格子也算完全淹没。

输入格式

从标准输入读入。第一行是三个整数 m,n,vm,n,v。随后按从上到下、每行从左到右的顺序给出 mnmn 个整数 hi,jh_{i,j}。原输入排版中,一行至多给出同一行格子的 2020 个高度;若某行格子的高度没有写完,会在下一行继续,下一行格子的高度则另起一行。

输出格式

向标准输出输出一行两个整数:最终的水面高度,以及完全淹没的格子中陆地的总体积。后者可能为 00。

4 5 33
2 2 2 2 2
1 3 4 3 2
2 3 5 3 2
2 4 1 1 2
4 43

样例解释

最终水面高度为 44。完全淹没的格子中,海拔为 1,2,3,41,2,3,4 的格子分别有 3,10,4,23,10,4,2 个。它们的陆地总体积为 1×3+2×10+3×4+4×2=431\times 3+2\times 10+3\times 4+4\times 2=43。

数据范围与约定

1≤m,n≤4001\le m,n\le 400,1≤hi,j≤10 0001\le h_{i,j}\le 10\,000,1≤v≤1091\le v\le 10^9。当水面达到高度 HH 时,容纳的水量为 ∑i=1m∑j=1nmax⁡(0,H−hi,j)\sum_{i=1}^m\sum_{j=1}^n\max(0,H-h_{i,j})。本地正式数据的最终水面高度均为整数。