Preface:

The 100th blog Festival

Title:

mxy is addicted to a spicy chicken game.
The game map is a n*n rectangle, with a number on each unit grid, representing the life body in the current position
Number, as a scout, mxy's task is to calculate the total number of people in the upper left and lower right corner of her position (no
Including her ranks).
Note that as a scout, mxy is not included in the number of creatures on the map.

Input:

The first line has two integers n and t. (1≤n≤1000，1≤t≤1000)
Next N lines, n integers in each line represent the number of life bodies on each unit lattice a. (1≤a≤100)
Next row t, two integers xi, yi for each row, represent the position of mxy on the map at different times.

Output:

Row T, an integer in each row, represents the total number of people in the upper left corner and the lower right corner where mxy is at the current time.

Sample input:

4 1
0 1 2 0
3 2 0 0
1 2 3 2
0 0 0 10
3 3

Sample output:

16

Train of thought:

80 points for simulation, 100 points for prefix and

Code × 1 (simulation):

//So obviously TLE
#include<cstdio>
#include<iostream>
#define rr register optimization
using namespace std;
long long n,m,a[10000][10000],x,y,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	scanf("%d",&a[i][j]);
	for(rr int xhcs=1;xhcs<=m;xhcs++)
	{
		scanf("%d%d",&x,&y);
		ans=0;
		for(rr long long i=1;i<=x-1;i++)
		for(rr long long j=1;j<=y-1;j++)
		ans+=a[i][j];//Add up top left
		for(rr long long i=x+1;i<=n;i++)
		for(rr long long j=y+1;j<=n;j++)
		ans+=a[i][j];//Accumulate bottom right
		printf("%d\n",ans); //output
	}
	return 0;
}

Code #2:

#include<cstdio>
#include<iostream>
#define rr register
using namespace std;
long long n,m,f[10000][10000],x,y,ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
	  scanf("%d",&x);
	  f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+x;//Prefix Sum
	}
	for(rr int xhcs=1;xhcs<=m;xhcs++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",f[x-1][y-1]+f[n][n]-f[x][n]-f[n][y]+f[x][y]);//Output [x-1][y-1] represents the number of columns on the previous row 
	} 
	return 0;
}