791 . 都市更新

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hehe

User's AC Ratio

96.0% (24/25)

Submission's AC Ratio

68.2% (30/44)

Tags

apcsc apcsc-dp

Description

在一塊方方正正的土地中，市長準備進行都市更新。這塊土地是 N×M 的矩形，左上角座標 (0,0)，左下角座標 (N−1,0)，右上角座標 (0,M−1)，右下角座標 (N−1,M−1)。每一個座標 (i,j) 的位置都有一棟價值 aij 的建築物，一旦這個位置被都更，這棟建築就要被剷平。

市長想選一塊方正的矩形區域作為都更預定地，其中左上角為 (u,l)，右下角為 (d,r)，矩形兩軸平行都市邊界。他一共會提出 Q 種方案，想問你每種方案分別要剷除多少價值的建築物。

Input Format

輸入第一行是三個以空白分隔的整數 N,M,Q，分別代表都市的長寬和市長提出的方案數。

接下來有 N 行每行 M 個以空白分割的整數，其中第 i 行第 j 個數字表示 ai−1,j−1。

接下來 Q 行，每行四個以空白分割的整數 u,l,d,r，代表市長提出的都更方案。

輸入保證 1≤N,M≤500，1≤aij≤109，1≤Q≤300000，0≤u≤d<N，0≤l≤r<M。

Output Format

輸出 Q 行，每行包含一個整數，代表該筆詢問需要剷除建築的價值。

Sample Input 1

2 3 2
1 3 5
2 4 6
0 0 1 1
0 1 1 1

Sample Output 1

10
7

Sample Input 2

3 3 3
1 3 5
6 8 7
2 4 9
1 1 2 1
0 1 2 2
0 0 2 2

Sample Output 2

12
36
45

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2
1 3000 524288 65536 1 2
2 3000 524288 65536 2
3 3000 524288 65536 2
4 3000 524288 65536 2
5 3000 524288 65536 2
6 3000 524288 65536 2
7 3000 524288 65536 2
8 3000 524288 65536 2
9 3000 524288 65536 2
10 3000 524288 65536 2
11 3000 524288 65536 2
12 3000 524288 65536 2
13 3000 524288 65536 2
14 3000 524288 65536 2
Submit
Back to Top