Pagini recente » Cod sursa (job #672478) | Cod sursa (job #90906) | Cod sursa (job #3207145) | Cod sursa (job #1227284) | Cod sursa (job #3207063)
#include <fstream>
#include <stack>
const int NMAX=1005;
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
void manacher(int [], int [], int);
int ans[NMAX][NMAX], a[NMAX][NMAX];
int p[NMAX], dr[NMAX], stt[NMAX];
int n, m;
stack <int> st;
int main()
{
int i, j, maxim=0;
fin>>n>>m;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
fin>>a[i][j];
}
manacher(ans[i], a[i], m);
}
for(j=1; j<=m; j++)
{
for(i=1; i<=n; i++)
{
while(!st.empty() && ans[st.top()][j]>ans[i][j])
{
dr[st.top()]=i;
st.pop();
}
st.push(i);
}
while(!st.empty())
{
dr[st.top()]=n+1;
st.pop();
}
for(i=n; i>=1; i--)
{
while(!st.empty() && ans[st.top()][j]>ans[i][j])
{
stt[st.top()]=i;
st.pop();
}
st.push(i);
}
while(!st.empty())
{
stt[st.top()]=0;
st.pop();
}
for(i=1; i<=n; i++)
{
maxim=max(maxim, (dr[i]-stt[i]-1)*(2*ans[i][j]-1));
}
}
fout<<maxim<<'\n';
return 0;
}
void manacher(int ans[], int v[], int lg)
{
int i;
int dr=0, st=0;
for(i=1; i<=lg; i++)
{
if(dr<i) ans[i]=1;
else ans[i]=min(ans[dr+st-i], dr-i+1);
while(true)
{
if(i-ans[i]<0 || i+ans[i]>lg) break;
if(v[i-ans[i]]==v[i+ans[i]]) ans[i]++;
else break;
}
ans[i]--;
if(dr<=ans[i])
{
dr=i+ans[i];
st=i-ans[i];
}
}
for(i=1; i<=lg; i++) ans[i]++;
}