Pagini recente » Cod sursa (job #2704703) | Cod sursa (job #2982581) | Cod sursa (job #3037789) | Borderou de evaluare (job #243670) | Cod sursa (job #2941423)
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>
#define NMAX 203
#define MOD 555557
using namespace std;
int n, m;
char mat[NMAX][NMAX];
int dp[NMAX][NMAX];//dp[i][j] nr maxim de 0 de pe col j in sus
int sus[NMAX], jos[NMAX];//aria celui mai mare dreptunghi de deasupra i/ sub i
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
void solve() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (mat[i][j] == '0')
{
dp[i][j] = 1 + dp[i - 1][j];//cresc practic nr de 0 de pe col i
}
else
{
dp[i][j] = 0;//se reseteaza secv
}
}
sus[i] = jos[i] = 0;
}
for (int i = 1; i <= n; i++) {
//setez linia de sus
for (int j = i; j <= n; j++) {
//in j setez linia de jos a dreptunghiului
int nr = 0;//numarul de coloane consecutive unde pot sa imi formez un dreptunghi
for (int k = 1; k <= m; k++) {
//in k am coloana dreptunghiului
if (dp[j][k] >= j - i + 1)
{
nr++;
}
else
{
nr = 0;
}
int aria = nr * (j - i + 1);
//reactualizez deasupra j
sus[j] = max(sus[j], aria);
//reactualizez sub i
jos[i] = max(jos[i], aria);
}
}
}
//iau maximul secvenntial din vectori
for (int i = 2; i <= n; i++)
{
sus[i] = max(sus[i], sus[i - 1]);
}
for (int i = n - 1; i >= 1; i--)
{
jos[i] = max(jos[i], jos[i + 1]);
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; i++)
{
fin >> mat[i] + 1;
}
solve();
int sol = 0;
for (int i = 1; i <= n; i++)
{
sol = max(sol, jos[i + 1] + sus[i]);
}
fout << sol;
return 0;
}