Pagini recente » Cod sursa (job #541908) | Cod sursa (job #1691515) | Cod sursa (job #2741165) | Cod sursa (job #54251) | Cod sursa (job #2663477)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
vector<int> manacher(vector<int> v){
int n=v.size();
vector<int> d(n);
for(int i=0, l=0, r=-1;i<n;++i){
int k=(i>r)?1:min(d[l+r-i],r-i+1);
while(0<=(i-k)&&(i+k<n)&&v[i-k]==v[i+k]) k++;
d[i]=k--;
if(i+k>r){
l=i-k;
r=i+k;
}
}
return d;
}
int ans=0;
int main(){
int n, m;
fin>>n>>m;
vector<int> sol[n];
for(int i=0;i<n;++i){
vector<int> v(m);
for(int j=0;j<m;++j){
fin>>v[j];
}
sol[i]=manacher(v);
}
for(int i=0;i<m;++i){
stack<int> s;
int st[n], dr[n];
for(int j=0;j<n;++j){
while(!s.empty()&&sol[s.top()][i]>=sol[j][i]) s.pop();
if(s.empty()) st[j]=0;
else st[j]=s.top()+1;
s.push(j);
}
while(!s.empty()) s.pop();
for(int j=n-1;j>=0;--j){
while(!s.empty()&&sol[s.top()][i]>=sol[j][i]) s.pop();
if(s.empty()) dr[j]=n-1;
else dr[j]=s.top()-1;
s.push(j);
}
for(int j=0;j<n;++j){
int dist=dr[j]-st[j]+1;
ans=max(ans, dist*(2*sol[j][i]-1));
}
}
fout<<ans<<"\n";
return 0;
}