3986853_ac_282ms_8544k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

int matrix[1025][1025];
int sum[1025][1025];

int f(int i, int j)
{
	if (i < 0 || j < 0)
		return 0;
	return sum[i][j];
}

int main()
{
	int cas;
	int i, j, d, n;
	int x, y, z;

	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d", &d);
		for (i = 0; i < 1025; i++)
		{
			for (j = 0; j < 1025; j++)
			{
				matrix[i][j] = 0;
			}
		}
		scanf("%d", &n);
		while (n--)
		{
			scanf("%d%d%d", &x, &y, &z);
			matrix[x][y] = z;
		}
		sum[0][0] = matrix[0][0];
		for (i = 1; i < 1025; i++)
		{
			sum[0][i] = matrix[0][i] + sum[0][i-1];
			sum[i][0] = matrix[i][0] + sum[i-1][0];
		}
		for (i = 1; i < 1025; i++)
		{
			for (j = 1; j < 1025; j++)
			{
				sum[i][j] = sum[i-1][j] + sum[i][j-1] + matrix[i][j] - sum[i-1][j-1];
			}
		}
		int max = 0, x, y, tmp;
		for (j = 1024 - d; j >= d; j--)
		{
			for (i = 1024 - d; i >= d; i--)
			{
				tmp = f(j + d, i + d)  - f(j + d, i - d - 1) - f(j - d - 1, i + d) + f(j - d - 1, i - d - 1);
				if (tmp >= max)
				{
					max = tmp;
					x = j;
					y = i;
				}
			}
		}
		printf("%d %d %d\n", x, y, max);
	}
	return 0;
}