Cod sursa(job #1340723)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 11 februarie 2015 23:35:05
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include<fstream>
using namespace std;
int n, m, i, j, maxim, nr, ii, jj;
char a[202][202];
int s[202][202], sus[202], jos[202];
int maxi(int a, int b){
    if(a > b){
        return a;
    }
    else{
        return b;
    }
}
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            fin>> a[i][j];
            a[i][j] -= '0';
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            s[i][j] = s[i-1][j] + a[i][j];
        }
    }
    for(ii = 1; ii <= n; ii++){
        for(i = ii; i <= n; i++){
            nr = 0;
            for(j = 1; j <= m; j++){
                if(s[i][j] - s[ii-1][j] == 0){
                    nr++;
                    sus[i] = maxi(sus[i], nr * (i - ii + 1));
                    jos[ii] = maxi(jos[ii], nr * (i - ii + 1));
                }
                else{
                    nr = 0;
                }
            }
        }
    }
    for(i = 2; i <= n; i++){
        sus[i] = maxi(sus[i], sus[i-1]);
    }
    for(i = n - 1; i >= 1; i--){
        jos[i] = maxi(jos[i], jos[i+1]);
    }
    for(i = 1; i <= n; i++){
        maxim = maxi(maxim, sus[i] + jos[i+1]);
    }
    for(i = 1; i <= n; i++){
        sus[i] = 0;
        jos[i] = 0;
        for(j = 1; j <= m; j++){
            s[i][j] = 0;
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            s[i][j] = s[i][j-1] + a[i][j];
        }
    }
    for(jj = 1; jj <= m; jj++){
        for(j = jj; j <= m; j++){
            nr = 0;
            for(i = 1; i <= n; i++){
                if(s[i][j] - s[i][jj-1] == 0){
                    nr++;
                    sus[j] = maxi(sus[j], nr * (j - jj + 1));
                    jos[jj] = maxi(jos[jj], nr * (j - jj + 1));
                }
                else{
                    nr = 0;
                }
            }
        }
    }
    for(j = 2; j <= m; j++){
        sus[j] = maxi(sus[j], sus[j-1]);
    }
    for(j = m - 1; j >= 1; j--){
        jos[j] = maxi(jos[j], jos[j+1]);
    }
    for(j = 1; j <= m; j++){
        maxim = maxi(maxim, sus[j] + jos[j+1]);
    }
    fout<< maxim;
    return 0;
}