Pagini recente » Cod sursa (job #273891) | Rating Stanciu Sebastian (sstan) | Cod sursa (job #261034) | Cod sursa (job #971503) | Cod sursa (job #2739964)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
const int NMAX = 202;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
char s[NMAX + 1];
int N, M,
DP[NMAX][NMAX], A[NMAX][NMAX],
up[NMAX], down[NMAX],
leftt[NMAX], rightt[NMAX];
void read()
{
f >> N >> M;
for(int i = 1; i <= N; i++)
{
f >> s + 1;
for(int j = 1; j <= M; j++)
A[i][j] = s[j] - '0';
}
}
void creare_DP_in_jos()
{
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
DP[i][j] = (A[i][j] == 0 ? DP[i - 1][j] + 1 : 0);
}
void creare_DP_in_sus()
{
for(int i = 1; i <= M; i++)
DP[N + 1][i] = 0;
for(int i = N; i >= 1; i--)
for(int j = 1; j <= M; j++)
DP[i][j] = (A[i][j] == 0 ? DP[i + 1][j] + 1 : 0);
}
int arie(int l)
{
stack<int>S;
for (int i = 1; i <= M; ++i)
{
while (S.size() > 0 && DP[l][i] <= DP[l][S.top()])
S.pop();
leftt[i] = S.size() == 0 ? 1 : S.top() + 1;
S.push(i);
}
while (S.size() > 0) S.pop();
for (int i = M; i >= 1; --i)
{
while (S.size() > 0 && DP[l][i] <= DP[l][S.top()])
S.pop();
rightt[i] = S.size() == 0 ? M : S.top() - 1;
S.push(i);
}
int area_max = 0;
for(int i = 1; i <= M; i++)
{
int area = DP[l][i] * (rightt[i] - leftt[i] + 1);
if(area > area_max)
area_max = area;
}
return area_max;
}
void dp_up()
{
for(int i = 1; i <= N; i++)
up[i] = arie(i);
}
void dp_down()
{
for(int i = N; i >= 1; i--)
down[i] = arie(i);
}
int answer_Ox()
{
for(int i = 2; i <= N; i++)
if(up[i - 1] > up[i])
up[i] = up[i - 1];
//
for(int i = N - 1; i >= 1; i--)
if(down[i + 1] > down[i])
down[i] = down[i + 1];
//
int maxx_2_areas=-1;
down[N+1]=0;
for(int i=1;i<=N;i++)
{
int area=up[i]+down[i+1];
if(area>maxx_2_areas)
maxx_2_areas=area;
}
return maxx_2_areas;
}
void swap(int &a, int &b)
{
a = a ^ b;
b = b ^ a;
a = a ^ b;
}
void Rotate()
{
static int B[NMAX][NMAX];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
B[M - j + 1][i] = A[i][j];
swap(N, M);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
A[i][j] = B[i][j];
}
void solve()
{
creare_DP_in_jos();
dp_up();
creare_DP_in_sus();
dp_down();
}
int main()
{
read();
//
solve();
int rasp1 = answer_Ox();
Rotate();
solve();
int rasp2 = answer_Ox(); ///de fapt Oy
//
g << max(rasp1, rasp2);
return 0;
}