Pagini recente » Cod sursa (job #2566194) | Cod sursa (job #2651465) | Cod sursa (job #1973905) | Cod sursa (job #215763) | Cod sursa (job #2461100)
#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#define NMAX 1000
#define inf 1000000000
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n, m;
int a[NMAX+10][NMAX+10], v[NMAX+10], b[NMAX+10][NMAX+10], st[NMAX+10], dr[NMAX+10], sol;
vector <int> s;
stack <int> stiva;
int main()
{
f >> n >> m;
for(int i=1; i<=n; i++)
{ for(int j=1; j<=m; j++)
f >> a[i][j];
memset(v, 0, sizeof(v));
s.clear();
int val1 = inf+1, val2 = inf+2, val3 = inf+3;
s.push_back(val1);
for(int j=1; j<=m; j++)
{ s.push_back(val2);
s.push_back(a[i][j]);
}
s.push_back(val2);
s.push_back(val3);
int C=0, R=0;
for(int j=1; j<s.size()-1; j++)
{ int ogl = 2*C-j;
if(j < R) v[j] = min(R-j, v[ogl]);
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*m; j+=2) b[i][j/2] = v[j] / 2 * 2 + 1;
}
for(int j=1; j<=m; j++)
{ memset(st, 0, sizeof(st));
memset(dr, 0, sizeof(dr));
while(!stiva.empty()) stiva.pop();
stiva.push(1);
for(int i=2; i<=n; 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);
}
while(!stiva.empty()) stiva.pop();
stiva.push(n);
dr[n] = n+1;
for(int i=n-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] = n + 1;
stiva.push(i);
}
for(int i=1; i<=n; i++) sol = max(sol, b[i][j]*(dr[i]-st[i]-1));
}
g << sol << '\n';
return 0;
}