C. 网格图路径问题

    传统题 文件IO:dis 1000ms 256MiB

网格图路径问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

ない

题目描述

  • 给定一张 nnmm 列的网格图,为了方便,我们约定 (xi,yi)(x_{i},y_{i}) 表示网格图第 ii 行第 jj 列,
  • 每个格子有一个整数权值 ai,ja_{i,j},注意格子的权值可以是负数
  • 给定 qq 个人位于网格图上,第 ii 个人的初始位置在 (xi,yi)(x_i, y_i),注意不保证每个人初始位置互不相同,
  • 定义某人走一步为:
    • 若这个人当前坐标在 (x,y)(x,y),则将该人移动至 (x+1,y),(x1,y),(x,y+1),(x,y1)(x+1,y),(x-1,y),(x,y+1),(x,y-1) 其中之一,
    • 设移动后到达 (x,y)(x^{\prime},y^{\prime}),此时需要满足 1xn,1ym1\leq x^{\prime}\leq n,1\leq y^{\prime}\leq m
    • 在任意时刻,允许任意多个人位于同一个位置。
  • 定义一个人的权值为其走若干步后所有经过的格子的权值和(包括起点和终点),若一个格子被经过 kk 次则其权值需要被累加 kk 次。
  • 特别地,若一个人没有走,则其权值为其初始位置格子的权值。
  • 定义总权值为每个人走若干步数,所有人权值的最大值,而不是求和。
  • 求最终所有人都走到同一个格子的最小总权值,或报告不存在最小总权值(即最小总权值为负无穷)。

输入格式

dis.in 读入。

  • 第一行包含三个正整数 n,m,qn, m, q
  • 接下来 nn 行,第 ii 行包含 mm 个整数 ai,1,ai,2,,ai,ma_{i, 1}, a_{i, 2}, \ldots, a_{i, m},
  • 接下来 qq 行,第 ii 行包含两个正整数 xi,yix_i, y_i,表示第 ii 个人的初始位置在 (xi,yi)(x _ i, y _ i)

输出格式

输出到 dis.out

  • 输出一行一个整数表示最小总权值,
  • 特别地,若最小总权值不存在(即最小总权值为负无穷),输出 NO(区分大小写)。

输入输出样例

3 3 1
1 2 3
4 5 6
7 8 9
2 2
5
3 3 2
1 2 3
4 5 6
7 8 9
2 2
3 3
15
3 3 3
1 4 -3
4 -1 4
7 8 9
1 1
2 2
3 3
10
3 3 9
1 4 -3
4 -1 4
7 8 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
11
3 3 3
-1 4 4
4 -1 4
7 8 -1
1 1
1 1
1 1
-1
3 3 3
1 4 -5
4 -1 4
7 8 9
1 1
2 2
3 3
NO

样例解释

【样例解释 1】 总权值最小的情况是第一个人不走,此时经过点只有 (2,2)(2,2),所以答案为 a2,2=5a_{2,2}=5

【样例解释 2】

总权值最小的情况是两个人走到 (2,3)(2,3),路线分别为 (2,2)(2,3)(2,2)\rightarrow (2,3)(3,3)(2,3)(3,3) \rightarrow (2,3),答案为 $\max(a_{2,2}+a_{2,3},a_{3,3}+a_{2,3}) = \max(11, 15) = 15$。

【样例解释 5】

总权值最小的情况是三个人都没有走,权值都为 a1,1=1a_{1,1}=-1,答案即为 1-1

【样例解释 6】

容易证明最小总权值为负无穷,所以输出 NO

数据范围

  • 1n,m1051\leq n,m\leq 10^5
  • 1nm1051\leq n m\leq 10^5
  • 1q501\leq q\leq 50
  • 1xin1 \le x_i \le n
  • 1yim1 \le y_i \le m
  • 1ai,j1091\leq |a_{i,j}|\leq 10^9

子任务

子任务编号 分值 限制
1 50 q=1q=1
2 N/A
  • 大样例下载
  • 编号为 ii 的大样例满足编号为 ii 的子任务的限制

24KOI 2025 体验赛 No.4

未参加
状态
已结束
规则
OI
题目
4
开始于
2025-6-22 13:00
结束于
2025-6-22 16:30
持续时间
3.5 小时
主持人
参赛人数
33