Pagini recente » Cod sursa (job #2759540) | Cod sursa (job #559407) | Cod sursa (job #1827683) | Cod sursa (job #559365) | Cod sursa (job #1345699)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
const int nmax= 1000;
int n, m;
int v[nmax+2], d[nmax+1][nmax+1], x[nmax+1], y[nmax+1];
stack <int> s;
int main( ) {
fin>>n>>m;
for ( int i= 1; i<=n; ++i ) {
for ( int j= 1; j<=m; ++j ) {
fin>>v[j];
}
v[m+1]= -1;
for ( int j= 1, right= 0, pos= 0; j<=m; ++j ) {
if ( j>right ) {
d[i][j]= 1;
int k;
for ( k= 1; v[j-k]==v[j+k]; ++k ) ; --k;
d[i][j]+= k, pos= j, right= j+k;
} else {
if ( j+d[i][2*pos-j]-1<right ) {
d[i][j]= d[i][2*pos-j];
} else {
d[i][j]= right-j+1;
int k;
for ( k= 1; v[2*j-right-k]==v[right+k]; ++k ) ; --k;
d[i][j]+= k, pos= j, right+= k;
}
}
}
}
int sol= n;
for ( int j= 1; j<=m; ++j ) {
for ( int i= 1; i<=n; ++i ) {
v[i]= d[i][j];
}
for ( ; !s.empty(); s.pop() ) ;
for ( int i= 1; i<=n; ++i ) {
for ( ; !s.empty() && v[i]<=v[s.top()]; s.pop() ) ;
if ( s.empty() ) x[i]= 1;
else x[i]= s.top()+1;
s.push(i);
}
for ( ; !s.empty(); s.pop() ) ;
for ( int i= n; i>=1; --i ) {
for ( ; !s.empty() && v[i]<=v[s.top()]; s.pop() ) ;
if ( s.empty() ) y[i]= n;
else y[i]= s.top()-1;
s.push(i);
}
for ( int i= 1; i<=n; ++i ) {
sol= max(sol, (y[i]-x[i]+1)*(2*v[i]-1));
}
}
fout<<sol<<"\n";
return 0;
}