4024 - 跳水

题目描述

在一个热闹的水上乐园中,设计师打造了一个 M \times N1 \leq M, N \leq 500)的矩形泳池区域,每个格子代表一个泳池单元,拥有一个特定的水深值,范围在 010^9 之间。为了增加乐趣,乐园在某些泳池单元设置了跳水点,作为游客开始入水的起点。

为确保游客的安全和趣味性,乐园需要计算出每个跳水点的趣味值。

每个跳水点的趣味值定义为:满足以下条件的最小整数 C

  • 从该跳水点出发,游客可以移动到相邻的泳池单元(向北、南、东、西四个方向)。
  • 目标单元的水深与当前单元的水深差的绝对值不超过 C,游客才能安全的游到该区域。
  • 通过这样的移动,游客需要能够游到至少 T 个不同的泳池单元。

请帮助乐园管理者计算所有跳水点的趣味值之和。

输入

第一行包含三个整数 NMT,分别表示泳池网格的行数、列数,以及每个跳水点需要访问的最少泳池单元数量。

接下来 N 行,每行包含 M 个整数,表示每个泳池单元的水深值。

再接下来 N 行,每行包含 M 个整数,每个整数为 011 表示该泳池单元是跳水点0 表示不是。

输出

输出一行一个整数,表示所有跳水点的趣味值之和

样例

输入

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

输出

24

输入

6 6 15
10 30 50 70 90 110
12 32 52 72 92 112
14 34 54 74 94 114
16 36 56 76 96 116
18 38 58 78 98 118
20 40 60 80 100 120
1 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0

输出

60

输入

8 10 50
100 101 102 103 104 200 201 202 203 204
99 100 101 102 103 199 200 201 202 203
98 99 100 101 102 198 199 200 201 202
97 98 99 100 101 197 198 199 200 201
96 97 98 99 100 196 197 198 199 200
95 96 97 98 99 195 196 197 198 199
94 95 96 97 98 194 195 196 197 198
93 94 95 96 97 193 194 195 196 197
1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1

输出

288
说明

样例 1 说明

泳池区域是一个 3 \times 5 的网格,跳水点位于左上角 (1,1) 和右下角 (3,5),每个跳水点需要访问至少 10 个泳池单元。

  • 对于跳水点 (1,1),趣味值为 4,可以通过水深差不超过 4 的移动访问至少 10 个泳池单元。
  • 对于跳水点 (3,5),趣味值为 20,可以通过水深差不超过 20 的移动访问至少 10 个泳池单元。
  • 总趣味值之和为 4 + 20 = 24

数据范围

对于 20\% 的数据,满足 1 \leq N \leq 101 \leq M \leq 3001 \leq T \leq 2000

对于 100\% 的数据,满足 1 \leq N, M \leq 5001 \leq T \leq N \times M,每个泳池单元的水深值在 [0, 10^9] 之间,跳水点标记为 01

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题