Pagini recente » Cod sursa (job #1229776) | Cod sursa (job #836802) | Cod sursa (job #2780820) | Cod sursa (job #1223158) | Cod sursa (job #1046964)
#include <algorithm>
#include <fstream>
#include <string>
#include <stack>
using namespace std;
const int N=1003;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
char cit[20*N];
vector <int> a;
int p[N][2*N], dr[N], st[N];
int n, m;
int solve()
{
int i, j, sol=0;
stack <int> s;
for(j=1;j<=m;j++)
{
for(i=1;i<=n;i++)
{
while(!s.empty()&&p[s.top()][j]>=p[i][j])
{
dr[s.top()]=i-1;
s.pop();
}
if(!s.empty()) st[i]=s.top()+1;
else st[i]=1;
s.push(i);
}
while(!s.empty())
{
dr[s.top()]=n;
s.pop();
}
for(i=1;i<=n;i++) sol=max(sol, (p[i][j]*2+1)*(dr[i]-st[i]+1));
}
return sol;
}
int main()
{
int i, j, x;
char *l;
fin>>n>>m; fin.get();
for(i=1;i<=n;i++)
{
fin.getline(cit, 20*N);
a.clear();
a.push_back(-2);
l=cit;
for(j=1;j<=m;j++)
{
x=0;
for(;*l>='0'&&*l<='9';l++) x=10*x+*l-'0'; l++;
a.push_back(x);
}
a.push_back(-3);
int c=0, r=0;
for(j=1;j<=m;j++)
{
if(r>j) p[i][j]=min(r-j, p[i][2*c-j]);
while(j+p[i][j]+1<a.size()&&j-p[i][j]-1>=0&&a[j+p[i][j]+1]==a[j-p[i][j]-1]) p[i][j]++;
if(j+p[i][j]>r)
{
r=j+p[i][j];
c=j;
}
}
/*for(j=1;j<a.size()-1;j++)
{
//p[i][j]=(p[i][j]+1)/2;
fout<<p[i][j]<<" ";
}
fout<<"\n";*/
}
fout<<solve();
}