Pagini recente » Cod sursa (job #2450725) | Cod sursa (job #2779351) | Cod sursa (job #3186917) | Cod sursa (job #147470) | Cod sursa (job #2775955)
#include <fstream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define NMAX 205
using namespace std;
/**********************************/
/// INPUT / OUTPUT
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
/**********************************/
/// GLOBAL DECLARATIONS
int N, M, res;
int tower[NMAX];
int ans[NMAX];
char mat[NMAX][NMAX]; // 1 - up, 2 - right, 3 - down, 4 - left
char temp[NMAX][NMAX];
int up[NMAX], l[NMAX], down[NMAX], r[NMAX];
/**********************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/**********************************/
///-----------------------------------------------
inline void ReadInput()
{
f >> N >> M;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
f >> mat[i][j];
}
///-----------------------------------------------
void RotateMat()
{
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
temp[j][N - i + 1] = mat[i][j];
swap(N, M);
// for (int i = 1 ; i <= N ; ++ i)
// for (int j = 1 ; j <= M ; ++ j)
// mat[i][j] = temp[i][j];
memcpy(mat, temp, sizeof(mat));
}
///-----------------------------------------------
inline void PrintMat()
{
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= M; ++j)
g << mat[i][j];
g << "\n";
}
g << "\n";
}
///-----------------------------------------------
void GetArray(int rot)
{
memset(ans, 0, sizeof(ans));
memset(tower, 0, sizeof(tower));
stack<int> s;
for (int i = 1; i <= N; ++i)
{
for (int j = 0; j < M; ++j)
{
if (mat[i][j + 1] == '0')
tower[j]++;
else
tower[j] = 0;
if (s.empty() || tower[s.top()] <= tower[j])
{
s.push(j);
continue;
}
while (!s.empty() && tower[s.top()] > tower[j])
{
int tp = s.top();
s.pop();
if (s.empty())
ans[i] = max(ans[i], tower[tp] * j);
else
ans[i] = max(ans[i], tower[tp] * (j - s.top() - 1));
}
s.push(j);
}
while (!s.empty())
{
int top = s.top();
s.pop();
if (s.empty())
ans[i] = max(ans[i], tower[top] * M);
else
ans[i] = max(ans[i], tower[top] * (M - s.top() - 1));
}
ans[i] = max(ans[i], ans[i - 1]);
}
switch (rot)
{
case 1:
memcpy(up, ans, sizeof(up));
break;
case 2:
memcpy(l, ans, sizeof(l));
break;
case 3:
memcpy(down, ans, sizeof(down));
break;
case 4:
memcpy(r, ans, sizeof(r));
break;
default:
break;
}
}
///-----------------------------------------------
inline void Solution()
{
// PrintMat();
GetArray(1);
RotateMat();
// PrintMat();
GetArray(2);
RotateMat();
// PrintMat();
GetArray(3);
RotateMat();
// PrintMat();
GetArray(4);
RotateMat();
// PrintMat();
for (int i = 1 ; i <= N ; ++ i)
{
res = max(res, up[i] + down[N - i]);
}
for (int j = 1 ; j <= M ; ++ j)
{
res = max(res, l[j] + r[N - j]);
}
}
///-----------------------------------------------
inline void Output()
{
g << res;
}
///-----------------------------------------------
int main()
{
ReadInput();
Solution();
Output();
return 0;
}