Cod sursa(job #1468638)

Utilizator cojocarugabiReality cojocarugabi Data 6 august 2015 16:22:43
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("bmatrix.in");
ofstream fo("bmatrix.out");
char c[205][205];
int dp[2][205][205];
int d[205];
int d1[205];
int d2[205];
int n,m;
//e - maxx the best
void go(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);
        }
        for (int j = 1;j <= m;++j)
            dp[ok][i][j] = max(0,(i - d[j]) * (d2[j] - d1[j] - 1));
    }
}
int main(void)
{
    fi>>n>>m;
    for (int i = 1;i <= n;++i) fi>>(c[i]+1);
    int ans = 0;
    go(0);
    for (int i = 1;i <= n/2;++i)
        for (int j = 1;j <= m;++j) swap(c[i][j],c[n-i+1][j]);
    go(1);
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            ans = max(ans,dp[0][i][j] + dp[1][n - i][j]);
    return fo << ans << '\n',0;
}