1916.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream.h>
#include <string.h>

int a[1030][1030];
int main()
{
	int test,d,n,i,max,j,temp,x,y,now;
	cin>>test;
	while(test--)
	{
		cin>>d;
		cin>>n;
		memset(a,0,sizeof(a));
		for(i=0;i<n;i++)
		{
			cin>>x>>y;
			cin>>a[x][y];
		}
		max=-1;
		for(i=1;i<1025;i++)
		{
			a[i][0]+=a[i-1][0];
			a[0][i]+=a[0][i-1];
		}
		temp=2*d+1;
		for(i=1;i<1025;i++)
			for(j=1;j<1025;j++) {
				a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
				if(i>=temp&&j>=temp) {
					now=a[i][j]-a[i-temp][j]-a[i][j-temp]+a[i-temp][j-temp];
					if(now>max) {
						max=now;
						x=i-d;
						y=j-d;
					}
				}
			}
		cout<<x<<" "<<y<<" "<<max<<endl;
	}
	return 0;
}