Pagini recente » Cod sursa (job #856170) | Cod sursa (job #252653) | Cod sursa (job #1091134) | Cod sursa (job #2116374) | Cod sursa (job #1003627)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define LL long long
#define NMAX 1007
using namespace std;
int D[NMAX][NMAX], Last, Nr, n, m, a[NMAX][NMAX], Mat[NMAX][NMAX];
stack < int > Stiva;
void Manacher(int Lung, int A[], int Ind){
for(int i = 1; i <= Lung; ++ i){
if(i == 1){
D[Ind][i] = 1;
Last = 1;
}
else
D[Ind][i] = max(min(D[Ind][Last - (i - Last)] - 1, Last + D[Ind][Last] - i), 1);
int St = i - D[Ind][i], Dr = i + D[Ind][i];
while(St >= 1 && Dr <= Lung && A[St] == A[Dr]){
++ D[Ind][i];
-- St;
++ Dr;
}
if(i + D[Ind][i] > Last + D[Ind][Last])
Last = i;
}
}
int main(){
int Dr, Maxim = -1;
freopen("dreptpal.in", "r", stdin);
freopen("dreptpal.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= m; ++ j)
scanf("%d", &a[i][j]);
Manacher(m, a[i], i);
}
/**for(int i = 1; i <= n; ++ i, printf("\n"))
for(int j = 1; j <= m; ++ j)
printf("%d ", D[i][j]);**/
for(int i = 1; i <= m; ++ i){
while(! Stiva.empty())
Stiva.pop();
for(int j = 1; j <= n; ++ j){
while(! Stiva.empty())
if(D[Stiva.top()][i] >= D[j][i])
Stiva.pop();
else
break;
if(Stiva.empty())
Dr = 0;
else
Dr = Stiva.top();
Stiva.push(j);
Mat[j][i] = (j - Dr) * ((D[j][i] * 2) - 1);
}
while(! Stiva.empty())
Stiva.pop();
for(int j = n; j >= 1; -- j){
while(! Stiva.empty())
if(D[Stiva.top()][i] >= D[j][i])
Stiva.pop();
else
break;
if(Stiva.empty())
Dr = n + 1;
else
Dr = Stiva.top();
Stiva.push(j);
Maxim = max(Maxim, (Dr - j - 1) * (D[j][i] * 2 - 1) + Mat[j][i]);
}
}
printf("%d", Maxim);
return 0;
}