Cod sursa(job #1788339)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 25 octombrie 2016 21:54:03
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <cstdio>
#define MAXN 210

using namespace std;

int n, m, a[MAXN][MAXN], aux[MAXN][MAXN];
int best[MAXN]; /// cel mai mare dreptunghi plin cu 0 care se termina pe linia i
int st[MAXN], val[MAXN], h[MAXN], rez;
char s[MAXN];

void read()
{
    scanf("%d %d\n", &n, &m);
    for (int i = 1; i <= n; i++) {
		gets(s+1);
		for (int j = 1; j <= m; j++)
			a[i][j] = s[j]-'0';
    }
}

void solve()
{
    for (int i = 1; i <= max(n, m); i++)
        h[i] = val[i] = best[i] = 0;
    for (int i = 1; i <= n; i++) {
		st[st[0] = 1] = 0;
        for (int j = 1; j <= m; j++) {
			if (a[i][j] != 0) h[j] = 0;
			else h[j]++;
            while (st[0] > 1 && h[st[st[0]]] >= h[j])
				st[0]--;
			val[j] = st[st[0]];
			st[++st[0]] = j;
        }
        st[st[0] = 1] = m+1;
		best[i] = best[i-1];
		for (int j = m; j >= 1; j--) {
            while (st[0]>1 && h[st[st[0]]] >= h[j])
				st[0]--;
			int v = st[st[0]];
			st[++st[0]] = j;
            if (h[j]*(v-val[j]-1) > best[i])
				best[i] = h[j]*(v-val[j]-1);
			for (int k = 1; k <= h[j]; k++)
				if (k*(v-val[j]-1) + best[i-k] > rez)
					rez = k*(v-val[j]-1) + best[i-k];
		}
    }
}

int main()
{
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);

    read();
	solve();
	swap(n, m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			aux[i][j] = a[j][i];
    for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			a[i][j] = aux[i][j];
    solve();
    printf("%d", rez);

	return 0;
}