Pagini recente » Cod sursa (job #2075278) | Cod sursa (job #1436523) | Cod sursa (job #718373) | Cod sursa (job #1803761) | Cod sursa (job #1597017)
#include <fstream>
#include <stack>
#include <utility>
using namespace std;
int n,m;
int a[1001][1001];
int p[1001][1001];
stack< pair<int,int> > S;
void Manacher(int A[],int P[])
{
int l = 0,r = -1;
for (int i = 1; i <= m; i++) {
if (i > r) P[i] = 1;
else P[i] = min(P[l+r-i],r-i+1);
int L = i - P[i] + 1;
int R = P[i] + i - 1;
while (L-1 >= 1 && R+1 <= m && A[L-1] == A[R+1]) L--,R++,P[i]++;
if (R > r)
r = R, l = L;
}
for (int i = 1; i <= m; i++)
P[i] = P[i] * 2 - 1;
}
int Solve(int j)
{
int Ret = n;
for (int i = 1; i <= p[1][j]; i++) S.push(make_pair(1,i));
for (int i = 2; i <= n; i++) {
if (S.empty() || S.top().second <= p[i][j]) S.push(make_pair(i,p[i][j]));
else {
int u = S.top().first;
while (!S.empty() && S.top().second > p[i][j]) {
Ret = max(Ret,(u-S.top().first+1)*S.top().second);
S.pop();
}
S.push(make_pair(i,p[i][j]));
}
}
int u = S.top().first;
while (!S.empty()) {
Ret = max(Ret,(u-S.top().first+1)*S.top().second);
S.pop();
}
return Ret;
}
int main()
{
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
fin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> a[i][j];
for (int i = 1; i <= n; i++)
Manacher(a[i],p[i]);
int Ans = n;
for (int j = 1; j <= m; j++)
Ans = max (Ans, Solve(j));
fout << Ans;
}