Pagini recente » Cod sursa (job #700167) | Cod sursa (job #647227) | Cod sursa (job #2161586) | Cod sursa (job #925999) | Cod sursa (job #2388103)
#include <iostream>
#include <fstream>
#include <queue>
#define fi first
#define se second
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
const int nmx=1005;
int n,i,j,c,r,nr,m,rez;
int v[nmx][nmx],l[nmx][nmx],st[nmx],dr[nmx];
typedef pair<int,int> per;
per p;
deque<per> dq;
int main() {
fin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
fin>>v[i][j];
for(i=1;i<=n;i++)
{
v[i][0]=-1;
v[i][m+1]=-2;
c=1;
r=1;
for(j=1;j<=m;j++)
{
if(j<=r)
l[i][j]=min(r-j, l[i][2*c-j]);
while(v[i][j+l[i][j]]==v[i][j-l[i][j]])
l[i][j]++;
l[i][j]--;
if(j+l[i][j]>r)
c=j, r=j+l[i][j];
}
}
for(j=1;j<=m;j++)
{
dq.push_back({l[1][j], 1});
st[1]=1;
for(i=2;i<=n;i++)
{
p={l[i][j], i};
while(!dq.empty() && p.fi<=dq.back().fi)
dq.pop_back();
if(dq.empty()) st[i]=i;
else st[i]=i-dq.back().se;
dq.push_back(p);
}
while(!dq.empty()) dq.pop_back();
dq.push_back({l[n][j], n});
dr[n]=1;
for(i=n-1;i>=1;i--)
{
p={l[i][j], i};
while(!dq.empty() && p.fi<=dq.back().fi)
dq.pop_back();
if(dq.empty()) dr[i]=n-i+1;
else dr[i]=dq.back().se-i;
dq.push_back(p);
}
while(!dq.empty()) dq.pop_back();
for(i=1;i<=n;i++)
rez=max(rez, (st[i]+dr[i]-1)*(2*l[i][j]+1));
}
fout<<rez<<"\n";
}