Pagini recente » Cod sursa (job #3002007) | Cod sursa (job #507886) | Cod sursa (job #2949701) | Cod sursa (job #1883488) | Cod sursa (job #2478406)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int NMAX = 1005;
const int INF = 2e9;
int m , n;
int a[NMAX][NMAX], v[NMAX], b[NMAX][NMAX] , st[NMAX] , dr[NMAX], ans;
vector<int>s;
stack<int>stiva;
void emptyStack()
{
while(!stiva.empty()) stiva.pop();
}
int main()
{
freopen("dreptpal.in","r",stdin);
freopen("dreptpal.out","w",stdout);
scanf("%d%d",&m,&n);
for(int i = 1 ; i <= m ; i++)
{
for(int j = 1 ; j <= n ; j++)
scanf("%d",&a[i][j]);
memset(v,0,sizeof(v));
s.clear();
s.push_back(INF+1);
for(int j = 1 ; j <= n ; j++)
{
s.push_back(INF+666013);
s.push_back(a[i][j]);
}
s.push_back(INF+666013);
s.push_back(INF+13);
int C,R;
C = R = 0;
for(int j = 1 ; j < s.size() - 1 ; j++)
{
v[j] = 0;
int mirror = 2*C-j;
if(j < R)
v[j] = min(R-j,v[mirror]);
while(s[j+v[j]+1] == s[j-v[j]-1]) v[j]++;
if(j+v[j] > R)
{
C = j;
R = j+v[j];
}
}
for(int j = 2 ; j <= 2*n ; j+=2)
b[i][j/2] = v[j]/2*2+1;
}
for(int j = 1 ; j <= n ; j++)
{
memset(dr,0,sizeof(dr));
memset(st,0,sizeof(st));
emptyStack();
stiva.push(1);
for(int i = 2 ; i <= m ; i++)
{
while(!stiva.empty() && b[i][j] <= b[stiva.top()][j])
stiva.pop();
if(!stiva.empty())
st[i] = stiva.top();
else
st[i] = 0;
stiva.push(i);
}
emptyStack();
stiva.push(m);
dr[m] = m+1;
for(int i = m-1 ; i >= 1 ; i--)
{
while(!stiva.empty() && b[i][j] <= b[stiva.top()][j])
stiva.pop();
if(!stiva.empty())
dr[i] = stiva.top();
else
dr[i] = m+1;
stiva.push(i);
}
for(int i = 1 ; i <= m ; i++)
ans = max(ans,b[i][j]*(dr[i]-st[i]-1));
}
printf("%d\n",ans);
return 0;
}