TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

87.0% (20/23)

Submission's AC Ratio

34.4% (33/96)

Tags

Description

之前北市賽曾經考過一題(TIOJ 1062),題目是這樣的:
現在有個r*c的地圖,亦即有r列、c行,每個格子有一些人在裡頭
定義一個人從某格到另一格的距離是他最少需要走幾格才能到達
定義這個午餐地點的代價為所有人從他們的位置到這格的距離和
現在要將選定某個格子作為午餐地點,試問最小的代價是多少?

這題目原本不難,不過現在由於物價上漲惹得午餐業者不爽了,他們決定把問題弄得難一點
而可憐的你,不但午餐變貴,你還要成為他們的出氣筒幫忙寫程式,寫不出來就沒午餐吃 :(
現在同樣地給你一個地圖以及上面每格有幾個人,對於每張地圖,你將要回答q個問題:
每個問題會給你一個矩形範圍
並詢問你對這個範圍內的人來說(僅考慮這個矩形內的人而不考慮其他人),選定一個午餐地點的代價最少是多少?

Input Format

每次輸入只有一組測試資料

第一行有兩個整數r, c ,代表地圖為r列c行
接下來的r列,每列有c個整數,表示地圖上每個位置的人數
之後有個整數q, 代表接下來的詢問數量
最後q行,每行有4個整數r1,r2,c1,c2 ,代表詢問以(r1,c1)為左上角,(r2,c2)為右下角的矩形區域

1 <= r, c <= 1,000
1 <= q <= 100,000
1 <= r1 <= r2 <= r
1 <= c1 <= c2 <= c

地圖上每一格的人數都在int的範圍內。

Output Format

對於每個詢問,請在單獨一行輸出一個整數代表午餐地點的最小代價。

Sample Input 1

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

Sample Output 1

0
15
17
1

Hints

Problem Source

原TIOJ1242 / Problem Provider: DarkKnight, Description by: kelvin

Subtasks

No. Testdata Range Score
1 0 8
2 1 8
3 2 8
4 3 8
5 4 8
6 5 8
7 6 8
8 7 8
9 8 8
10 9 8
11 10 8
12 11 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 6000 65536 262144 1
1 6000 65536 262144 2
2 6000 65536 262144 3
3 6000 65536 262144 4
4 6000 65536 262144 5
5 6000 65536 262144 6
6 6000 65536 262144 7
7 6000 65536 262144 8
8 6000 65536 262144 9
9 6000 65536 262144 10
10 6000 65536 262144 11
11 6000 65536 262144 12