cf D. Maximum Submatrix 2

http://codeforces.com/contest/376/problem/D

题意：给你一个矩阵，可以随意排列n行的次序，然后找出全部含有1的子矩阵。输出1的个数。

思路：c[i][j]表示在i列第j行的格子的右边连续的1的个数。对于每一列，排序c[i],然后比较c[i][j]*(n-j+1)与max1的大小，max1就是答案。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 5001
using namespace std;

char g[maxn][maxn];
int c[maxn][maxn];
int n,m;
int x[maxn];

int main()
{
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         memset(c,0,sizeof(c));
         for(int i=1; i<=n; i++)
         {
             scanf("%s",g[i]+1);
         }
         for(int i=1; i<=n; i++)
         {
             for(int j=1; j<=m; j++)
             {
                 if(g[i][j]=='1')
                 {
                      c[j][i]=c[j-1][i]+1;
                 }
             }
         }
         int max1=-1;
         for(int i=1; i<=m; i++)
         {
             sort(c[i]+1,c[i]+1+n);
             for(int j=1; j<=n; j++)
             {
                 if(c[i][j]*(n-j+1)>max1)
                 {
                     max1=c[i][j]*(n-j+1);
                 }
             }
         }
         cout<<max1<<endl;
     }
     return 0;
}