1321: 全为1面积最大正方形Ⅲ

完全没想到前缀和数组

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+10;
int num[N][N];
int pre[N][N];
int n,m;
bool judge(int mid){for(int i=mid;i<=n;i++){for(int j=mid;j<=m;j++){if (pre[i][j]-pre[i-mid][j]-pre[i][j-mid]+pre[i-mid][j-mid]==mid*mid)return true;}}return false;
}
int main(){scanf("%d%d",&n,&m);int x=max(n,m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&num[i][j]);pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+num[i][j];}}int l=0,r=x,mid;while(l<r){mid = l+(r-l+1)/2;if(judge(mid)) l=mid;else r=mid-1;}cout<<l*l;return 0;
}