Pagini recente » Cod sursa (job #993617) | Cod sursa (job #365035) | Cod sursa (job #1544204) | Cod sursa (job #1200510) | Cod sursa (job #1303736)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;
#define NMAX 1002
int a[NMAX][NMAX],st[NMAX],v[NMAX],c[NMAX],l[NMAX],r[NMAX];
void manacher(int s[], int p[], int n)
{
int R,C,i,j;
R=1;
C=1;
s[0]=-1;
s[n+1]=-2;
for(i=2;i<=n-1;i++) {
j=2*C-i;
if(i+p[j]<R)
p[i]=p[j];
else {
if(R>i)
p[i]=R-i;
else p[i]=0;
while(s[i+p[i]+1]==s[i-p[i]-1])
p[i]++;
}
if(i+p[i]>R) {
R=p[i]+i;
C=i;
}
}
}
int main ()
{
int n,m,i,j,p,sol;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
f>>n>>m;
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++)
f>>c[j];
manacher(c,a[i],m);
}
f.close();
sol=-1;
for(j=1;j<=m;j++) {
for(i=1;i<=n;i++)
v[i]=a[i][j];
p=0;
st[0]=0;
for(i=1;i<=n;i++) {
while(p && v[st[p]]>=v[i])
p--;
l[i]=st[p]+1;
st[++p]=i;
}
p=0;
st[0]=n+1;
for(i=n;i>=1;i--) {
while(p && v[st[p]]>=v[i])
p--;
r[i]=st[p]-1;
st[++p]=i;
}
for(i=1;i<=n;i++)
sol=max(sol,(2*v[i]+1)*(r[i]-l[i]+1));
}
g<<sol;
g.close();
return 0;
}