#589. 图图的游戏

【题目描述】：
图图正在玩一个智力游戏：有一个n×n 的01 方格，图图要从中选出一个面积最大的矩形区域，要求这个矩形区域不能有超过k个1。这么难的问题图图当然不会做了，他想让你帮帮他，你能解决这个问题吗？【输入描述】：
第一行包含2 个正整数n，k。接下来n 行每行n 个整数，表示这个01方格。【输出描述】：
输出1 个整数，表示最大面积。【样例输入】：
5 4
1 0 1 0 1
0 1 0 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
【样例输出】：
12
【时间限制、数据范围及描述】：
时间：1s 空间：256M对于40%的数据，1≤n≤10；对于70%的数据，1≤n≤51；对于100%的数据，1≤n≤501，0≤k≤n×n。本题n^4的算法想必是人人都会写的,直接一个矩阵前缀和就行了,然后我就想到了二分第四维,结果还是90,最后没想到的是尺取大法居然比二分快得多.
只想说一句:尺取大法好！！！Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<deque>
using namespace std;
const int N=505;
int c[N][N],n,q,f[N][N];
int read() {int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;
}
int calc(int r1,int c1,int r2,int c2){return f[r2][c2]-f[r2][c1-1]-f[r1-1][c2]+f[r1-1][c1-1];
}
int main(){n=read();q=read();for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c[i][j]=read();f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+c[i][j];}}int ans=0;for(int i=1;i<=n;i++){for(int k=1;k<=i;k++){int l=1;for(int j=1;j<=n;j++){while(calc(k,l,i,j)>q){l++;}int x=i-k+1;int y=j-l+1;ans=max(ans,x*y);}}}printf("%d\n",ans);return 0;
}