[USACO Mar08]挖湖

成绩 0 开启时间 2013年01月17日 星期四 11:15
折扣 0.8 折扣时间 2013年01月17日 星期四 11:15
允许迟交 关闭时间 2013年01月17日 星期四 11:15
输入文件 makelake.in 输出文件 makelake.out

Farmer John想让奶牛们帮他在农场上挖个湖。FJ将他想改造成湖的草地划成了R (3 <= R <= 100)行C (3 <= C <= 100)列,每个格子都是6英尺*6英尺的正方形,并且有个单位为英寸的全格平均高度elev_rc (10 <= elev_rc <= 5000)。

此外,为了他的计划,FJ教会了所有奶牛一项特殊技:战争践踏:)。技能作用范围为3*3的、左上角为R_s,C_s (1 <= R_s <= R-2; 1 <= C_s <= C-2)的正方形区域,效果为把这块区域的地面高度压低D_s (1 <= D_s <= 40)英寸。 不过,技能实际的效果不是很尽人意:事实上,奶牛只能把该区域中高度大于最大高度 - D_s的草地高度压低到最大高度 - D_s,也就是说,区域中可能出现没有被压过的,或者被压低高度小于D_s的格子。

FJ清楚草地上各格子目前的高度,奶牛们发动技能的N (1 <= N <= 20000)个地点,以及挖完湖注完水后的水面高度E (0 <= E <= 5000)。他希望你帮忙计算一下湖中水的总体积(以立方英寸为单位)。这个值保证不超过2,000,000,000。湖周围是一圈很高的堤坝,你不用担 心水会从湖的边缘溢出。

考虑一块将变成湖的4*6的草地。其中每块地的初始高度如下图所示:

                     列编号
                 1  2  3  4  5  6
        第1行:  28 25 20 32 34 36
        第2行:  27 25 20 20 30 34
        第3行:  24 20 20 20 20 30
        第4行:  20 20 14 14 20 20

地图的右上角有一块高地,最高点高度为36,左上角也有个最高点高度为28的土包。第4行中间的地势比较低。在奶牛发动一次参数为“1 4 4”的战争践踏后,草地变成了如下的样子:

                 1  2  3  4  5  6
        第1行:  28 25 20 32 32 32
        第2行:  27 25 20 20 30 32
        第3行:  24 20 20 20 20 30
        第4行:  20 20 14 14 20 20

注意,只有3块草地被压得低了些;其余格子由于本来高度就比较低,根本没有被压过。如果随后FJ指挥奶牛们在左上角发动一次技能,参数为“1 1 10”,技能施放后草地的状态如下:

                 1  2  3  4  5  6
        第1行:  18 18 18 32 32 32
        第2行:  18 18 18 20 30 32
        第3行:  18 18 18 20 20 30
        第4行:  20 20 14 14 20 20
  

如果按设计,湖的水面高度为22英寸,那么草地各部分的水深为:

                 1  2  3  4  5  6
        第1行:   4  4  4 -- -- --
        第2行:   4  4  4  2 -- --
        第3行:   4  4  4  2  2 --
        第4行:   2  2  8  8  2  2

草地上各块水深的和为66。因为每块草地面积为6英尺*6英尺,于是池中水的总体积为66 * 72英寸 * 72英寸 = 342,144立方英寸(1英尺 = 12英寸)。

请你写个程序,帮FJ计算湖中水的体积。

程序名: makelake

输入格式:

  • 第1行: 4个用空格隔开的整数:R,C,E,N
  • 第2..R+1行: 第i+1行为C个用空格隔开的整数,描述了第i行各列的草地高度
  • 第R+2..R+N+1行: 第i+R+1行为3个用空格隔开的整数R_s、C_s、D_s,为奶牛们依次发动的技能的参数

输入样例 (makelake.in):

4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10

输入说明:

输入即为题中给的例子。

输出格式:

  • 第1行: 输出1个整数,为挖好后的湖中水的体积,单位为立方英寸

输出样例 (makelake.out):

342144