Pagini recente » Borderou de evaluare (job #182900) | Borderou de evaluare (job #2895838) | Borderou de evaluare (job #2208275) | Borderou de evaluare (job #753442) | Cod sursa (job #2412652)
#include <fstream>
#include <algorithm>
#include <stack>
const int NMAX=1005;
using namespace std;
ifstream cin ("dreptpal.in");
ofstream cout ("dreptpal.out");
int v[NMAX],z[NMAX],pal[NMAX][NMAX];
int n,m;
void palindrom(int lin)
{
int r=0,c=0;
for(int j=1; j<=m; ++j){
if(j>r){
while(j-z[j]>0 && j+z[j]<=m && v[j+z[j]]==v[j-z[j]])
++z[j];
}
else{
int leftover=min(z[2*c-j],r-j);
z[j]=leftover;
while(j-z[j]>0 && j+z[j]<=m && v[j+z[j]]==v[j-z[j]])
++z[j];
}
if(j+z[j]>r){
r=j+z[j];
c=j;
}
pal[lin][j]=z[j]*2-1;
}
for(int j=1; j<=m; ++j)
z[j]=0;
}
int rectangle(int col)
{
// lucrez cu pal[1][col] ... pal[n][col]
stack <int> st;
int l[NMAX],r[NMAX];
for(int i=1; i<=n; ++i){
while(!st.empty() && pal[st.top()][col]>=pal[i][col])
st.pop();
if(st.empty())
l[i]=0;
else
l[i]=st.top();
st.push(i);
}
while(!st.empty())
st.pop();
for(int i=n; i>=1; --i){
while(!st.empty() && pal[st.top()][col]>=pal[i][col])
st.pop();
if(st.empty())
r[i]=n+1;
else
r[i]=st.top();
st.push(i);
}
int maxim=(r[1]-l[1]-1)*pal[1][col];
for(int i=2; i<=n; ++i)
maxim=max(maxim,(r[i]-l[i]-1)*pal[i][col]);
return maxim;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; ++i){
for(int j=1; j<=m; ++j)
cin>>v[j];
palindrom(i);
}
int sol=0;
for(int j=1; j<=m; ++j)
sol=max(sol,rectangle(j));
cout<<sol<<'\n';
return 0;
}