Pagini recente » Cod sursa (job #3273419) | Cod sursa (job #140534) | Cod sursa (job #84908) | Cod sursa (job #127279) | Cod sursa (job #636008)
Cod sursa(job #636008)
#include<cstdio>
#include<fstream>
#include<algorithm>
using namespace std;
int nr[1010][1010],pal[1010][1010];
int N,M,Sol;
typedef pair<int,int> PII;
PII S[1010],lung[1010];
void calc_pal(int lin){
int i,j;
for(i=1;i<=M;++i){
for(j=0;i-j>0 && i+j<=M;++j){
if(nr[lin][i-j]==nr[lin][i+j])
pal[lin][i]=j;
else
break;
}
}
}
void calc_h(int C){
int i,st=1,arie=0;
S[1].first=pal[1][C];
S[1].second=1;
for(i=2;i<=N;++i){
while(S[st].first>pal[i][C] && st>0){
lung[S[st].second].first=i-S[st].second-1;
S[st].first=S[st].second=0;
--st;
}
S[++st].first=pal[i][C];
S[st].second=i;
}
while(st>0){
lung[S[st].second].first=N-S[st].second;
S[st].first=S[st].second=0;
--st;
}
S[1].first=pal[N][C];
S[1].second=N;
st=1;
for(i=N-1;i>0;--i){
while(S[st].first>pal[i][C] && st>0){
lung[S[st].second].second=S[st].second-i-1;
S[st].first=S[st].second=0;
--st;
}
S[++st].first=pal[i][C];
S[st].second=i;
}
while(st>0){
lung[S[st].second].second=S[st].second-1;
S[st].first=S[st].second=0;
--st;
}
for(i=1;i<=N;++i){
if((lung[i].first+lung[i].second+1) * (2*pal[i][C]+1)>arie)
arie=(lung[i].first+lung[i].second+1) * (2*pal[i][C]+1);
lung[i].first=lung[i].second=0;
}
if(arie>Sol)
Sol=arie;
}
int main(){
//freopen("dreptpal.in","r",stdin);
//freopen("dreptpal.out","w",stdout);
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int i,j;
//scanf("%d%d",&N,&M);
f>>N>>M;
for(i=1;i<=N;++i){
for(j=1;j<=M;++j)
//scanf("%d",&nr[i][j]);
f>>nr[i][j];
}
for(i=1;i<=N;++i)
calc_pal(i);
for(i=1;i<=M;++i)
calc_h(i);
//printf("%d\n",Sol);
g<<Sol<<'\n';
fclose(stdin);
fclose(stdout);
return 0;
}