【题目描述】：

图图正在玩一个智力游戏：有一个n×n 的01 方格，图图要从中选出一个面积最大的矩形区域，要求这个矩形区域不能有超过k个1。

这么难的问题图图当然不会做了，他想让你帮帮他，你能解决这个问题吗？

【输入描述】：

第一行包含2 个正整数n，k。

接下来n 行每行n 个整数，表示这个01方格。

【输出描述】：

输出1 个整数，表示最大面积。

【样例输入】：

5 41 0 1 0 10 1 0 0 01 0 1 0 01 1 1 1 10 0 1 0 1

【样例输出】：

12

【时间限制、数据范围及描述】：

时间：1s 空间：256M

对于40%的数据，1≤n≤10；

对于70%的数据，1≤n≤51；

对于100%的数据，1≤n≤501，0≤k≤n×n。

 

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int a[1005][1005],sum[1005][1005];int n,m;int read(){ int a=0,b=1; char ch=getchar(); while((ch<48||ch>57)&&ch!='-'){ ch=getchar(); } if(ch=='-'){ b=-1; ch=getchar(); } while(ch<48||ch>57){ ch=getchar(); } while(ch>47&&ch<58){ a=a*10+ch-48; ch=getchar(); } return a*b;}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=read(); sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } } int ans=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ int l=1; for(int r=1;r<=n;r++){ while(sum[j][r]-sum[j][l-1]-sum[i-1][r]+sum[i-1][l-1]>m&&l<=r)l++; if(l<=r)ans=max(ans,(j-i+1)*(r-l+1)); } } } printf("%d\n",ans); return 0;}