Cod sursa(job #1468711)

Utilizator cojocarugabiReality cojocarugabi Data 6 august 2015 19:24:48
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
char c[205][205];
int dp[4][205];
int d[205];
int d1[205];
int d2[205];
int n,m;
//e - maxx the best
void go01(int ok)
{
    stack < int > s;
    for (int i = 1;i <= m;++i) d[i] = 0;
    for (int i = 1;i <= n;++i)
    {
        for (int j = 1;j <= m;++j)
            if (c[i][j] == '1') d[j] = i;
        while (!s.empty()) s.pop();
        for (int j = 1;j <= m;++j)
        {
            while (!s.empty() && d[s.top()] <= d[j]) s.pop();
            d1[j] = (s.empty() ? 0:s.top());
            s.push(j);
        }
        while (!s.empty()) s.pop();
        for (int j = m;j;--j)
        {
            while (!s.empty() && d[s.top()] <= d[j]) s.pop();
            d2[j] = (s.empty() ? m+1:s.top());
            s.push(j);
        }
        dp[ok][i] = dp[ok][i-1];
        for (int j = 1;j <= m;++j)
            dp[ok][i] = max(dp[ok][i],(i - d[j]) * (d2[j] - d1[j] - 1));
    }
}
void go23(int ok)
{
    stack < int > s;
    for (int i = 1;i <= n;++i) d[i] = 0;
    for (int j = 1;j <= m;++j)
    {
        for (int i = 1;i <= n;++i)
            if (c[i][j] == '1') d[i] = j;
        while (!s.empty()) s.pop();
        for (int i = 1;i <= n;++i)
        {
            while (!s.empty() && d[s.top()] <= d[i]) s.pop();
            d1[i] = (s.empty() ? 0:s.top());
            s.push(i);
        }
        while (!s.empty()) s.pop();
        for (int i = n;i;--i)
        {
            while (!s.empty() && d[s.top()] <= d[i]) s.pop();
            d2[i] = (s.empty() ? n + 1:s.top());
            s.push(i);
        }
        dp[ok][j] = dp[ok][j-1];
        for (int i = 1;i <= n;++i)
            dp[ok][j] = max(dp[ok][j],(j - d[i]) * (d2[i] - d1[i] - 1));
    }
}
int main(void)
{
    fi>>n>>m;
    for (int i = 1;i <= n;++i) fi>>(c[i]+1);
    int ans = 0;
    go01(0);
    for (int i = 1;i <= n/2;++i) swap(c[i],c[n-i+1]);
    go01(1);
    for (int i = 1;i <= n/2;++i) swap(c[i],c[n-i+1]);
    go23(2);
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m/2;++j) swap(c[i][j],c[i][m-j+1]);
    go23(3);
    for (int i = 1;i < n;++i)
            ans = max(ans,dp[0][i] + dp[1][n-i]);
    for (int i = 1;i < m;++i)
            ans = max(ans,dp[2][i] + dp[3][m-i]);
    return fo << ans << '\n',0;
}