{"problem":{"name":"[厦门小学生 C++ 2023] 数据核心","description":{"content":"Sora 有一块神奇的数据核心，这块数据核心里有 $n\\times m$ 个数据块，这些数据块组成了一个 $n\\times m$ 的矩阵。 在数据核心中，每个数据块都有一个强度 $a_{i,j}$，代表这个数据块存在数据核心中时会提供多少的运算力。但是随着时间的推移，数据核心中有一些数据块出现了硬件老化，有些数据块的强度是一个负数，继续保留过多的老化数据块会影响数据核心的使用效率，所以 Sora","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4157"},"statements":[{"statement_type":"Markdown","content":"Sora 有一块神奇的数据核心，这块数据核心里有 $n\\times m$ 个数据块，这些数据块组成了一个 $n\\times m$ 的矩阵。\n\n在数据核心中，每个数据块都有一个强度 $a_{i,j}$，代表这个数据块存在数据核心中时会提供多少的运算力。但是随着时间的推移，数据核心中有一些数据块出现了硬件老化，有些数据块的强度是一个负数，继续保留过多的老化数据块会影响数据核心的使用效率，所以 Sora 决定从原本的数据核心的矩阵中，先确定一个数据块作为新数据核心的左上角，其位置为 $(x, y)$ ，向右下方切割出一块数据核心（子矩阵），以保证其使用效率。\n\n但是 Sora 是一个有着天马行空想象力的科学家，她想知道在确定了新的数据核心左上角的数据块的情况下，其位置为 $(x, y)$，新的数据核心（子矩阵）能够获得的最大运算力是多少。\n\n当然她的问题很多，有 $Q$ 次询问，每次询问都会给出一个位置 $(x, y)$，你需要算出以这个位置为左上角的新数据核心对应的最大运算力。\n\n## Input\n\n第一行两个整数 $n,m$，表示原始数据核心的大小。\n\n接下来 $n$ 行，每行 $m$ 个整数，对应的是每个数据块的强度 $a_{i,j}$。\n\n第 $n+2$ 行一个整数 $Q$，表示询问次数。\n接下来 $Q$ 行，每行两个整数 $x,y$，表示新数据核心的左上角数据块在原数据核心中位于第 $x$ 行第 $y$ 列。\n\n## Output\n\n输出 $Q$ 行，每行一个整数，表示对应询问的最大运算力。\n\n[samples]\n\n## Background\n\n本试题为 2023 年厦门市小学生 C++ 语言**复赛**试题，数据为洛谷自造。\n\n**初赛**为笔试。\n\n## Note\n\n### 样例解释\n\n- 第一个询问对应的新数据核心是 $(1,1)$ 到 $(5,5)$。\n- 第二个询问对应的新数据核心是 $(2,2)$ 到 $(5,5)$。\n- 第三个询问对应的新数据核心是 $(3,3)$ 到 $(5,4)$。\n- 第四个询问对应的新数据核心是 $(5,1)$ 到 $(5,4)$。\n- 第五个询问对应的新数据核心是 $(5,5)$ 到 $(5,5)$。\n\n### 数据范围\n\n- 对于 $20\\%$ 的数据，$n\\times m \\leq 500$，$Q \\leq 500$，$|a_{i,j}| \\leq 10^5$。\n- 对于 $50\\%$ 的数据，$n\\times m \\leq 5000$，$Q \\leq 5000$，$|a_{i,j}| \\leq 10^5$。\n- 对于 $80\\%$ 的数据，$n\\times m \\leq 10000$，$Q \\leq 10000$，$|a_{i,j}| ≤ 10^5$。\n- 对于 $100\\%$ 的数据，$n\\times m \\leq 100000$，$Q \\leq 100000$，$|a_{i,j}| \\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4157","tags":["动态规划 DP","2023","福建","前缀和","科创活动","小学活动"],"sample_group":[["5 5\n1 -1 1 -1 1\n2 2 2 -1 2\n1 1 2 -1 -1\n-1 -1 2 2 1\n1 1 1 1 -1\n6\n1 1\n2 2\n3 3\n2 4\n5 1\n5 5","16\n12\n7\n2\n4\n-1"]],"created_at":"2026-03-03 11:09:25"}}