Cod sursa(job #1310056)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 6 ianuarie 2015 13:12:32
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<fstream>
using namespace std;
int n, m, i, j, u, maxim, maxim1, maxim2, x, k;
int s[202][202], c[201];
char a[201][201];
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(j = 1; j <= m; j++){
        s[1][j] = a[1][j];
        s[n+1][j] = -1;
    }
    for(i = 2; i <= n; i++){
        for(j = 1; j <= m; j++){
            if(a[i][j] == 1){
                s[i][j] = 0;
            }
            else{
                s[i][j] = s[i-1][j] + 1;
            }
        }
    }
    for(k = 1; k < n; k++){
        maxim1 = 0;
        maxim2 = 0;
        for(i = 1; i <= k; i++){
            u = 1;
            c[1] = 1;
            for(j = 2; j <= m + 1; j++){
                x = c[u];
                while(s[i][c[u]] > s[i][j]){
                    if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
                        maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
                    }
                    u--;
                }
                u++;
                c[u] = j;
            }
        }
        for(i = k + 1;  i <= n; i++){
             u = 1;
            c[1] = 1;
            for(j = 2; j <= m + 1; j++){
                x = c[u];
                while(s[i][c[u]] > s[i][j]){
                    if((x - c[u] + 1) * (s[i][c[u]]) > maxim2){
                        maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
                    }
                    u--;
                }
                u++;
                c[u] = j;
            }
        }
        if(maxim1 + maxim2  > maxim){
            maxim = maxim1 + maxim2;
        }
    }
    for(k = 1; k < m; k++){
        maxim1 = 0;
        maxim2 = 0;
        for(i = 1; i <= n; i++){
            u = 1;
            c[1] = 1;
            for(j = 2; j <= k; j++){
                x = c[u];
                while(s[i][c[u]] > s[i][j]){
                    if((x - c[u] + 1) * (s[i][c[u]]) > maxim1){
                        maxim1 = (x - c[u] + 1) * (s[i][c[u]]);
                    }
                    u--;
                }
                u++;
                c[u] = j;
            }
        }
        for(i = 1;  i <= n; i++){
             u = 1;
            c[1] = k + 1;
            for(j = k + 2; j <= m; j++){
                x = c[u];
                while(s[i][c[u]] > s[i][j]){
                    if((x - c[u] + 1) * (s[i][c[u]]) > maxim2){
                        maxim2 = (x - c[u] + 1) * (s[i][c[u]]);
                    }
                    u--;
                }
                u++;
                c[u] = j;
            }
        }
        if(maxim1 + maxim2  > maxim){
            maxim = maxim1 + maxim2;
        }
    }
    fout<< maxim;
    return 0;
}