Cod sursa(job #3276677)

Utilizator zavragiudavid dragoi zavragiu Data 14 februarie 2025 08:49:00
Problema BMatrix Scor 4
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");

/**
6 8
10000000
10000000
10000000
11100011
00100011
00100011
00111111
*/

struct dreptunghi
{
    ///stanga sus, dreapta jos
    int is, js, id, jd, arie;
}vec[40002];

bool a[202][202];
int n, m, sp[202][202], k;

bool Alaturate(int a, int b)
{
    int i, j, x, y, p, q, c, d;
    i = vec[a].is; j = vec[a].js;
    x = vec[a].id; y = vec[a].jd;
    p = vec[b].is; q = vec[b].js;
    c = vec[b].jd; d = vec[b].jd;
    ///sus
    if(c == i - 1 && !(d < j || q > y)) return true;
    ///dreapta
    if(q == y + 1 && !(d < i || p > x)) return true;
    ///jos
    if(p == x + 1 && !(d < j || q > y)) return true;
    ///stanga
    if(d == j - 1 && !(d < i || p > x)) return true;
    return false;
}

int main()
{
    int i, j, x, y;
    string s;
    fin >> n >> m;
    for(i = 1; i <= n; i++)
    {
        fin >> s;
        for(j = 1; j <= m; j++)
            a[i][j] = s[j-1] - '0';
    }
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            sp[i][j] = sp[i-1][j-1] + sp[i][j-1] + sp[i-1][j] + a[i][j] - 2 * sp[i-1][j-1];
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
            for(x = 1; x <= i; x++)
                for(y = 1; y <= j; y++)
                    if(sp[i][j] - sp[i][y-1] - sp[j][x-1] + sp[x-1][y-1] == 0)
                    {
                        k++;
                        vec[k].is = x; vec[k].js = y;
                        vec[k].id = i; vec[k].jd = j;
                        vec[k].arie = (i - x + 1) * (j - y + 1);
                    }
    int ans = -1;
    for(i = 1; i < k; i++)
        for(j = i + 1; j <= k; j++)
            if(Alaturate(i, j)) ans = max(ans, vec[i].arie + vec[j].arie);
    if(ans == -1)
        for(i = 1; i <= k; i++)
            ans = max(ans, vec[i].arie);
    fout << ans;
    return 0;
}