题目：P1736

为什么$n = 2500$然后$O(n^2)$了几次会$TLE$，而且还WA了，大佬求调

思路：

存每条斜边的最上面那个的坐标和最下面的那个坐标，遇到1就搜，再用二维前缀和判断这个正方形里是不是只有对角线上的1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2505;
int n, m, a[N][N], sum[N][N], tot, mx = INT_MIN;
pair<pair<int, int> ,pair<int, int>> G[N * N];
void op(int x, int y, int mode)
{
	if (mode == 1)//存最下面的坐标
	{
		G[tot].second.first = x;
		G[tot].second.second = y;
	}
	else//存最上面的坐标
	{
		G[tot].first.first = x;
		G[tot].first.second = y;
	}
	return;
}
void dfs(int x, int y, int mode)
{
	int dy, dx = 1;
	if (mode == 1) dy = -1;//向左下搜
	else dy = 1;//向右下搜
	if (x > n || x < 1 || y > m || x < 1) return;
	if (a[x][y] == 0) return;
	x += dx, y += dy;
	if (x > n || x < 1 || y > m || y < 1) 
	{
		op(x - dx, y - dy, 1);//如果后面没了，存最下面
		return;
	}
	if (a[x][y] == 0)
	{
		op(x - dx, y - dy, 1);//如果后面是0，存最下面
		return;
	}
	dfs(x, y, mode);
}
int sumd(int x1, int y1, int x2, int y2)
{
	if (x1 > x2) swap(x1, x2);
	if (y1 > y2) swap(y1, y2);
	return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> a[i][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 <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			bool flag1 = true, flag2 = true;
			if (a[i][j] == 0) continue;
			if (i >= 2)
			{
				if (j >= 2) if (a[i - 1][j - 1] == 1) flag2 = false;
				if (j <= n - 1) if (a[i - 1][j + 1] == 1) flag1 = false;
			}//小剪枝，不搜重复的斜线
			if (flag1)
			{
				tot++;
				op(i, j, 2);
				dfs(i, j, 1);
			}
			if (flag2)
			{
				tot++;
				op(i, j, 2);
				dfs(i, j, 2);
			}
		}
	}
	for (int i = 1; i <= tot; i++)
	{
		int x1 = G[i].first.first, y1 = G[i].first.second, x2 = G[i].second.first, y2 = G[i].second.second;
		int sm = sumd(x1, y1, x2, y2);
		if (sm != abs(x1 - x2) + 1) continue;
		mx = max(mx, sm);
	}
	if (mx == INT_MIN) mx = 0;
	cout << mx << endl;
	return 0;
}