Pagini recente » Rating Stefan Zamfir (stefzamfir) | Cod sursa (job #833566)
Cod sursa(job #833566)
#include <fstream>
#include <stack>
#include <cstring>
#define MAX 215
using namespace std;
char sir[MAX];
int V[MAX][MAX], Up[MAX][MAX], Down[MAX][MAX], Right[MAX], Left[MAX];
int aux[MAX][MAX], dpUp[MAX], dpDown[MAX];
int N, M, rez;
void CheckSides(int V[MAX][MAX], int L[MAX], int R[MAX], int line)
{
stack<int> stk;
for(int i = 1; i <= M; i++)
{
while(!stk.empty() && V[line][stk.top()] > V[line][i]) R[stk.top()] = i - 1, stk.pop();
if(stk.empty()) L[i] = 1;
else L[i] = stk.top() + 1;
stk.push(i);
}
while(!stk.empty()) R[stk.top()] = M, stk.pop();
}
void solve()
{
memset(dpUp, 0, sizeof(dpUp));
memset(dpDown, 0, sizeof(dpDown));
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
if(!V[i][j]) Up[i][j] = Up[i - 1][j] + 1;
else Up[i][j] = 0;
for(int i = N; i; i--)
for(int j = 1; j <= M; j++)
if(!V[i][j]) Down[i][j] = Down[i + 1][j] + 1;
else Down[i][j] = 0;
for(int i = 1; i <= N; i++)
{
CheckSides(Up, Left, Right, i);
int part = 0;
for(int j = 1; j <= M; j++) part = max(part, Up[i][j] * (Right[j] - Left[j] + 1));
dpUp[i] = max(dpUp[i - 1], part);
}
for(int i = N; i; i--)
{
CheckSides(Down, Left, Right, i);
int part = 0;
for(int j = 1; j <= M; j++) part = max(part, Down[i][j] * (Right[j] - Left[j] + 1));
dpDown[i] = max(dpDown[i + 1], part);
}
for(int i = 1; i < N; i++) rez = max(rez, dpUp[i] + dpDown[i + 1]);
}
int main()
{
ifstream in("bmatrix.in");
in>>N>>M; in.get();
for(int i = 1; i <= N; i++)
{
in.getline(sir, MAX);
for(int j = 1; j <= M; j++) V[i][j] = sir[j - 1] - '0';
} in.close();
solve();
memcpy(aux, V, sizeof(aux));
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
V[j][i] = aux[i][j];
swap(N, M);
ofstream out("bmatrix.out"); out<<rez; out.close();
return 0;
}