Cod sursa(job #1730919)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 iulie 2016 20:21:10
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <stack>

using namespace std;
#define ll long long
#define llu long long unsigned
#define pb push_back
#define mp make_pair

//string problemName = "home";
//string inFile = problemName+".in";
//string outFile = problemName+".out";
//ifstream fin(inFile.c_str());
//ofstream fout(outFile.c_str());

const int N = 205;
char v[N][N];
int dph[N][N], dpst[N][N], dpdr[N][N];
int s[N];

int solve(int x1, int y1, int x2, int y2){
    int i,j;
    for(i = x1;i <= x2;i++){
        for(j = y1;j <= y2;j++){
            if(v[i][j] == '0'){
                dph[i][j] = dph[i-1][j]+1;
            }else{
                dph[i][j] = 0;
            }
        }
    }
    int e;
    for(i = x1;i <= x2;i++){
        e = 0;
        for(j = y1;j <= y2;j++){
            while(e > 0 && dph[i][j] <= dph[i][s[e]]){
                e--;
            }
            if(e == 0){
                dpst[i][j] = y1-1;
            }else{
                dpst[i][j] = s[e];
            }
            s[++e] = j;
        }
    }
    for(i = x1;i <= x2;i++){
        e = 0;
        for(j = y2;j >= y1;j--){
            while(e > 0 && dph[i][j] <= dph[i][s[e]]){
                e--;
            }
            if(e == 0){
                dpdr[i][j] = y2+1;
            }else{
                dpdr[i][j] = s[e];
            }
            s[++e] = j;
        }
    }
    int a,bst = 0;
    for(i = x1;i <= x2;i++){
        for(j = y1;j <= y2;j++){
            if(v[i][j] == '0'){
                a = dph[i][j]*(dpdr[i][j]-dpst[i][j]-1);
                if(a > bst){
                    bst = a;
                }
                dph[i][j] = dpdr[i][j] = dpst[i][j] = 0;
            }
        }
    }
    return bst;
}



int main(){
    int n,m,i,ans;
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
    ans = 0;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;i++){
        scanf("%s",v[i]+1);
    }
    for(i = 2;i <= m;i++){
        ans = max(ans, solve(1, 1, n, i-1) + solve(1, i, n, m));
    }
    for(i = 2;i <= n;i++){
        ans = max(ans, solve(1, 1, i-1, m) + solve(i, 1, n, m));
    }
    printf("%d",ans);
    return 0;
}