C++14(g++5.4) 解法, 执行用时: 355ms, 内存消耗: 48872K, 提交时间: 2019-11-17 17:59:45

#include<cstdio>
#include<cstring>
using namespace std;
int t,i,j,x,y,x1,y1,k,n,m,q,n1,m1;
int a[2000][2000];
long long b[2000][2000];
inline int max(int a,int b)
{
	return a>b?a:b;
}
inline int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	scanf("%d",&t);
	for (;t;--t)
	{
		scanf("%d%d",&n,&m);
		memset(a,0,sizeof(a));
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j) scanf("%d",&a[i-j+m][i+j-1]);
		n1=n+m-1;
		m1=n+m-1;
		for (i=1;i<=n1;++i)
			for (j=1;j<=m1;++j) b[i][j]=a[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];
		scanf("%d",&q);
		for (;q;--q)
		{
			scanf("%d%d%d",&x,&y,&k);
			x1=x-y+m;
			y1=x+y-1;
			printf("%lld\n",b[min(x1+k,n1)][min(y1+k,m1)]-b[max(x1-k-1,0)][min(y1+k,m1)]-b[min(x1+k,n1)][max(y1-k-1,0)]+b[max(x1-k-1,0)][max(y1-k-1,0)]);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 1390ms, 内存消耗: 9820K, 提交时间: 2019-11-17 16:16:15

# include <iostream>
# include <cstdio>

using namespace std;

long long A[1010][1010];

int main(void)
{
	//freopen("aaa.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);	
		for (int i=1;i<=n;i++)
		for (int j=1,a;j<=m;j++)
		{
			scanf("%d",&a);
			A[i][j] = A[i][j-1]+a;
		}
		int q,x,y,k;
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d%d%d",&x,&y,&k);
			long long ans=0;
			int r=min(y+k,m),l=max(1,y-k),up,low;
			ans+=A[x][r]-A[x][l-1];
			for (int i=k-1;i>=0;i--)
			{
				r = min(y+i,m);l = max(1,y-i);
				up = x-(k-i);
				if (up>=1) ans+=A[up][r]-A[up][l-1];
				low = x+(k-i);
				if (low<=n) ans+=A[low][r]-A[low][l-1];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}