Problem : 335 - 廷廷爭霸

Problem Statistics

Solved Member: 12　　Submission: 52　　User Tried: 12

Statement:

身為國家棟樑的廷廷正在研究一款回合制戰略遊戲(Turn-based strategy, TBS)。
遊戲地圖是一個 n*n 的方形棋盤，每一格代表一個根據地，當玩家併吞某一格殖民地時會得到固定的獲利!廷廷選了一張地圖，並且在遊戲開始前模擬 m 次的遊戲，每次模擬會進行下述事項:

一開始廷廷選擇併吞一格殖民地 (x,y)，接下來每個回合廷廷會往已佔領殖民地的上、下、左、右四個方位併吞，廷廷想要知道 z 個回合後他的總獲利為多少。

(要注意每執行完一次以後地圖會恢復原本的樣子，因此詢問間互相沒有關係，前面佔領某格的價值在後面的詢問中還可以再得到一次。但在同一次詢問中，一格的價值只能得到一次。)

Input:Output:

第 1 行有兩個整數 n,m 代表地圖大小為 n*n，接下來有 m 筆詢問。

第 2 到第 n+1 行每行有 n 個整數，第 i+1 行第 j 個數字 $a_{ij}$ 代表地圖上座標 (i,j) 被併吞時殖民地獲得的利益。接下來 m 行為廷廷模擬的遊戲，每筆詢問有三個正整數 x,y,z，代表起始的座標 (x,y) 以及回合數 z。

$1 \le n \le 1000$
$1 \le m \le n^2$
$0 \le a_{ij} \le 10^6$
$1 \le x,y,z \le n$

在佔分至少 50% 的測試資料中滿足：每個格子只會被最多一筆詢問問到而已

每筆詢問一行，輸出一個整數表示廷廷的總獲利。

Sample Input:Sample Output:

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

20
15

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2500ms	262144kb
1	2500ms	262144kb	10
2	2500ms	262144kb	10
3	2500ms	262144kb	10
4	2500ms	262144kb	10
5	2500ms	262144kb	10
6-1	2500ms	262144kb	10
6-2	2500ms	262144kb
7-1	2500ms	262144kb	10
7-2	2500ms	262144kb
8-1	2500ms	262144kb	10
8-2	2500ms	262144kb
9-1	2500ms	262144kb	10
9-2	2500ms	262144kb
10-1	2500ms	262144kb	10
10-2	2500ms	262144kb
10-3	2500ms	262144kb