Se consideră o matrice A cu următoarele proprietăţi:

• conţine n linii şi m coloane;
• conţine doar valorile 0 şi 1;
• pe fiecare linie valorile sunt plasate în ordine crescătoare.

Definim o submatrice determinată de perechea de linii L1 şi L2 (L1 ≤ L2) şi de perechea de coloane C1 şi C2 (C1 ≤ C2) ca fiind totalitatea elementelor matricei A[i,j] pentru care L1 ≤ i ≤ L2 şi C1 ≤ j ≤ C2.

Exemplu

submat1.in

3 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1

submat1.out

6

Explicație

Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:
0 0 0 1 1
0 0 0 0 1
0 1 1 1 1
atunci se observă că submatricea determinată de prima şi a doua linie şi de prima şi a treia coloană conţine 6 valori de 0 (6 fiind numărul maxim posibil).

#include <bits/stdc++.h>
using namespace std;
ifstream cin("submat1.in");
ofstream cout("submat1.out");
int main()
{
    int n , m , x , cntmax = 0 , f[1001]={0};
    cin >> n >> m;
    for(int i = 0 ; i < n; ++i)
        for(int j = 0 ; j < m ; ++j)
        {
            cin >> x;
            if(x==0) f[i]++;
        }
    for(int i = 1 ; i <= m ; ++i)
    {
        int cnt = 0;
        for(int j = 0  ; j < n ; ++j)
            if(f[j]>=i) cnt+=i;
        if(cnt > cntmax) cntmax = cnt;
    }
    cout << cntmax;
    return 0;
}