Pagini recente » Cod sursa (job #2758985) | Cod sursa (job #957649) | Cod sursa (job #2485009) | Cod sursa (job #2796809) | Cod sursa (job #638589)
Cod sursa(job #638589)
#include <fstream>
using namespace std;
const int NMAX = 1005;
int N, M, a[NMAX][NMAX];
int L[NMAX];
void work(int *s, int n)
{
int lim = 1, mid = 1;
L[1] = 1;
for (int i = 2; i <= n; ++i)
{
if (i > lim) lim = i, L[i] = 1;
else L[i] = min(L[2*mid - i], lim - i + 1);
if (i + L[i] - 1 == lim)
{
mid = i;
for (int l = i - L[i], r = i + L[i];l > 0 && r <= n && s[l] == s[r];--l, ++r)
++L[i], lim = r;
}
}
for (int i = 1;i <= n;++i) s[i] = L[i];
}
int stk[NMAX], up[NMAX], down[NMAX];
void solve()
{
int maxarea = 0;
for (int j=1;j<=M;++j)
{
int z=0;
stk[0] = 0; a[0][j] = 0;
for (int i=1;i<=N;++i)
{
while (a[stk[z]][j] >= a[i][j]) -- z;
up[i] = stk[z] + 1;
stk[++z] = i;
}
stk[z=0] = N+1; a[N+1][j] = 0;
for (int i = N; i>=1; --i)
{
while (a[stk[z]][j] >= a[i][j]) --z;
down[i] = stk[z] - 1;
stk[++z] = i;
}
for (int i=1;i<=N;++i)
{
int height = down[i] - up[i] + 1;
int area = (2*a[i][j] - 1)*height;
maxarea = max(maxarea, area);
}
}
ofstream fout("dreptpal.out");
fout<<maxarea<<"\n";
}
int main()
{
ifstream fin("dreptpal.in");
fin>>N>>M;
for (int i=1;i<=N;++i)
{
for (int j=1;j<=M;++j)
fin>>a[i][j];
work(a[i], M);
}
solve();
return 0;
}