Rover Loves FF14

Final Fantasy XIV(ff14) is a 3D massively multiplayer online role-playing game(MMORPG) developed by square Enix, a Japanese game developer. It is the fourteenth game work in the Final Fantasy series. Since it was published, ff14 has attracted many players with its grand stories, beautiful graphics ,fine-sounding soundtrack and rich game content.

Rover is a crazy ff14 player. Now, he decides to challenge the most difficult duty of this game: the Unending Coil of Bahamut (Ultimate) with his favorite role: Black Mage. The field of this duty is a grid with n rows and m columns. The grid point (i, j) in row i and column j contains a_i,j monsters. Rover is a player who attaches great importance to efficiency, so he decides to use his strongest Area of effect action: Foul, which could attack many monsters at a time.

The effect of this action is as follows: Each time Rover will choose a grid point (r, c) (representing the grid point in row r and column c), and then choose a range d. Monsters within grid point he chose d distance will be attacked (Note: the distance here refers to Manhattan distance. In other words, for each grid point (i, j), if it satisfies $|i-r|+|j-c|\leq d$ , all monsters located in grid point (i, j) will be attacked.

Rover is ready to use this action q times. Now he wants to know how many monsters will be attacked every time after he uses this action. Because Rover forgot to wear his best equipment, so monsters will not be killed after being attacked.

The first line contains three single integers $n,m,q (1≤n,m≤2000,1≤q≤10^6)$ — the number of rows, the number of columns in the grid, and the number of times Rover use the action.

The following n lines describe the grid. The i-th of the n lines contains m integers $a_{i,1},a_{i,2},…,a_{i,m} (0≤a_{i,j}≤10^9)$ — the number of monsters in the grid points.

Then, the following q lines describe the action. The i-th of the q lines contains three integers $r_i,c_i,d_i (1\leq r_i\leq n,1\leq c_i\leq m,0\leq d_i\leq 10^6)$ , represents Rover chooses the grid point in row r_iand column c_i, and attack all the monsters within the grid point d_i distance.

#include<bits/stdc++.h> using namespace std; const int N=4005; int n,m,q,a[N][N]; long long sum[N][N]; int main() { int x,y,z; scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&x); a[i+j][i-j+2000]=x; } for(int i=1;i<=4000;i++) for(int j=1;j<=4000;j++) { sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j]; } for(int i=1;i<=q;i++) { scanf("%d%d%d",&x,&y,&z); int a1=min(x+y+z,4000),b1=min(x-y+2000+z,4000),a2=max(x+y-z-1,0),b2=max(x-y+2000-z-1,0); printf("%lld\n",sum[a1][b1]-sum[a1][b2]-sum[a2][b1]+sum[a2][b2]); } }

详情