CodeForces 375B Maximum Submatrix 2

说来惭愧，虽然已经做了几场CF了，但这还是第一次挑战D题，还是Div.2 的D题. . . . . .

好了，下面来看题意。给出一个大小为N*M的只有‘0’和‘1’组成的矩阵，找出一个最大的只有‘1’组成的子矩阵。

对于每一个位置保存一下从左边到当前位置有多少个连续的‘1’，然后问题就从二维就变成了一维，剩下的就很简单了，不再赘述。

话说这个题虽然思路很明确但还是TLE了很多次。

一开始的Hash记录连续的 ‘1’ 的个数，一直卡在第21组数据上，然后改到二叉排序树，卡在了第38组。

然后又改回Hash，又把输入从两个for(;;)嵌套 + 一个 scanf("%1d") 改成了 一个for(;;) + 一个scanf("%s"),没想到竟然奇迹般的A掉了，

才跑了470ms+，话说这个scanf()有这么费时间嘛！发在这里提醒一下自己以后能用第二种输入方式就绝不用第一种. . . .

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #pragma comment(linker, "/STACK:1024000000"); #define LL long long int using namespace std; char Map[5010][5010]; int ans[5010][5010]; int mark[5010][5010]; int main() { int n,m,i,j; scanf("%d %d",&n,&m); for(i = 0;i < n; ++i) { memset(mark[i],0,sizeof(int)*(m+2)); } for(i = 0;i < n; ++i) { scanf("%*c%s",Map[i]); Map[i][0] -= '0'; ans[i][0] = Map[i][0]; mark[0][ans[i][0]] ++; for(j = 1;j < m; ++j) { Map[i][j] -= '0'; ans[i][j] = (Map[i][j] == 1   ans[i][j-1]+1 : 0); mark[j][ans[i][j]] ++; } } int Max = -1,temp,sum; for(j = 0;j < m; ++j) { sum = 0; for(i = m;i >= 1; --i) { if( (temp = (sum += mark[j][i])*i) > Max) Max = temp; } } if(Max == -1) Max = 0; cout<