#B4157. [厦门小学生 C++ 2023] 数据核心

    ID: 13120 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>动态规划 DP2023福建前缀和小学科创活动

[厦门小学生 C++ 2023] 数据核心

题目背景

本试题为 2023 年厦门市小学生 C++ 语言复赛试题,数据为洛谷自造。

初赛为笔试。

题目描述

Sora 有一块神奇的数据核心,这块数据核心里有 n×mn\times m 个数据块,这些数据块组成了一个 n×mn\times m 的矩阵。

在数据核心中,每个数据块都有一个强度 ai,ja_{i,j},代表这个数据块存在数据核心中时会提供多少的运算力。但是随着时间的推移,数据核心中有一些数据块出现了硬件老化,有些数据块的强度是一个负数,继续保留过多的老化数据块会影响数据核心的使用效率,所以 Sora 决定从原本的数据核心的矩阵中,先确定一个数据块作为新数据核心的左上角,其位置为 (x,y)(x, y) ,向右下方切割出一块数据核心(子矩阵),以保证其使用效率。

但是 Sora 是一个有着天马行空想象力的科学家,她想知道在确定了新的数据核心左上角的数据块的情况下,其位置为 (x,y)(x, y),新的数据核心(子矩阵)能够获得的最大运算力是多少。

当然她的问题很多,有 QQ 次询问,每次询问都会给出一个位置 (x,y)(x, y),你需要算出以这个位置为左上角的新数据核心对应的最大运算力。

输入格式

第一行两个整数 n,mn,m,表示原始数据核心的大小。

接下来 nn 行,每行 mm 个整数,对应的是每个数据块的强度 ai,ja_{i,j}

n+2n+2 行一个整数 QQ,表示询问次数。 接下来 QQ 行,每行两个整数 x,yx,y,表示新数据核心的左上角数据块在原数据核心中位于第 xx 行第 yy 列。

输出格式

输出 QQ 行,每行一个整数,表示对应询问的最大运算力。

5 5
1 -1 1 -1 1
2 2 2 -1 2
1 1 2 -1 -1
-1 -1 2 2 1
1 1 1 1 -1
6
1 1
2 2
3 3
2 4
5 1
5 5
16
12
7
2
4
-1

提示

样例解释

  • 第一个询问对应的新数据核心是 (1,1)(1,1)(5,5)(5,5)
  • 第二个询问对应的新数据核心是 (2,2)(2,2)(5,5)(5,5)
  • 第三个询问对应的新数据核心是 (3,3)(3,3)(5,4)(5,4)
  • 第四个询问对应的新数据核心是 (5,1)(5,1)(5,4)(5,4)
  • 第五个询问对应的新数据核心是 (5,5)(5,5)(5,5)(5,5)

数据范围

  • 对于 20%20\% 的数据,n×m500n\times m \leq 500Q500Q \leq 500ai,j105a_{i,j} \leq 10^5
  • 对于 50%50\% 的数据,n×m5000n\times m \leq 5000Q5000Q \leq 5000ai,j105a_{i,j} \leq 10^5
  • 对于 80%80\% 的数据,n×m10000n\times m \leq 10000Q10000Q \leq 10000ai,j105a_{i,j} ≤ 10^5
  • 对于 100%100\% 的数据,n×m100000n\times m \leq 100000Q100000Q \leq 100000ai,j109|a_{i,j}| \leq 10^9