Cod sursa(job #1808705)

Utilizator yosemiteYosemite yosemite Data 17 noiembrie 2016 23:36:18
Problema BMatrix Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
const int nMax = 203;
char s[nMax][nMax], aux[nMax][nMax];
int sum[nMax][nMax], h[nMax];
int St[nMax], Dr[nMax], dpup[nMax], dpdown[nMax];
int ans = 0;
stack <int> Stiva;
int n , m;
inline void Read() {
    f >> n >> m;
    for(int i = 1; i <= n; i++) {
        f >> (s[i] + 1);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            aux[i][j] = s[i][j];
        }
    }
}
inline void Prec() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            sum[i][j] = s[i][j] - '0';
            if(sum[i][j] == 0) {
                sum[i][j] = sum[i-1][j] + 1;
            }
            else {
                sum[i][j] = 0;
            }
        }
    }
}
inline void Query(int dp[]) {
    long long area = 0;
    for(int L = 1; L <= n; L++) {
        while(!Stiva.empty()) {
            Stiva.pop();
        }
        for(int i = 1; i <= m; i++) {
            h[i] = sum[L][i];
            while(!Stiva.empty() && h[Stiva.top()] >= h[i]) {
                Stiva.pop();
            }
            if(!Stiva.empty()) {
                St[i] = Stiva.top() + 1;
            }
            else {
                St[i] = i;
            }
            Stiva.push(i);
        }
        while(!Stiva.empty()) {
            Stiva.pop();
        }
        for(int i = m; i >= 1; i--) {
            while(!Stiva.empty() && h[Stiva.top()] >= h[i]) {
                Stiva.pop();
            }
            if(!Stiva.empty()) {
                Dr[i] = Stiva.top() - 1;
            }
            else {
                Dr[i] = i;
            }
            Stiva.push(i);
            area = max(area, (Dr[i] - St[i] + 1) * 1LL * h[i]);
        }
        dp[L] = max(1LL * dp[L-1], area);
    }
}
inline void Change() {
    for(int i = 1; i <= n / 2 + 1; i++) {
        for(int j = 1; j <= m; j++) {
            swap(s[i][j], s[n - i + 1][j]);
        }
    }
    Prec();
}
inline void Solve() {
    for(int i = 1; i < n; i++) {
        ans = max(ans, dpup[i] + dpdown[n - i]);
    }
}
inline void Rotate(){
    for(int i = 1; i <= n; i++) {
        for(int j = 1;  j <= m; j++) {
            s[i][j] = aux[j][n - i + 1];
        }
    }
    swap(n,m);
}
int main()
{
    Read();
    Prec();
    Query(dpup);
    Change();
    Query(dpdown);
    Solve();
    Rotate();
    Prec();
    Query(dpup);
    Change();
    Query(dpdown);
    Solve();
    g<< ans << "\n";
    return 0;
}