Pagini recente » Cod sursa (job #2361866) | Cod sursa (job #2834326) | igorj_4 | Cod sursa (job #194943) | Cod sursa (job #636761)
Cod sursa(job #636761)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 1024
int N, M, sol;
int A[maxn][maxn], D[maxn][maxn];
int V[maxn], ST[maxn], DR[maxn];
void calc_pal(int lin) {
int i, mxx;
D[lin][1] = 0; mxx = 1;
for(i=2; i<=M; i++) {
if(i < mxx + D[lin][mxx]) {
D[lin][i] = min(D[lin][mxx - (i - mxx)], mxx + D[lin][mxx] - i);
}
if(mxx + D[lin][mxx] <= i + D[lin][i]) {
mxx = i;
while(1 <= i - D[lin][i] - 1 && i + D[lin][i] + 1 <= M && A[lin][i + D[lin][i] + 1] == A[lin][i - D[lin][i] - 1]) {
D[lin][i]++;
}
}
}
}
int main() {
FILE *f1=fopen("dreptpal.in", "r"), *f2=fopen("dreptpal.out", "w");
int i, j, p;
fscanf(f1, "%d %d\n", &N, &M);
for(i=1; i<=N; i++) {
for(j=1; j<=M; j++) {
fscanf(f1, "%d", &A[i][j]);
}
}
for(i=1; i<=N; i++) {
calc_pal(i);
}
for(i=2; i<M; i++) {
for(j=1; j<=N; j++) {
V[j] = D[j][i];
}
V[0] = -1; ST[1] = 1;
for(j=2; j<=N; j++) {
p = j;
while(V[j] <= V[p-1]) {
p = ST[p-1];
}
ST[j] = p;
}
V[N+1] = -1; DR[N] = N;
for(j=N-1; j>=1; j--) {
p = j;
while(V[j] <= V[p+1]) {
p = DR[p+1];
}
DR[j] = p;
}
for(j=1; j<=N; j++) {
sol = max(sol, (2*V[j] + 1)*(DR[j] - ST[j] + 1));
}
}
fprintf(f2, "%d\n", sol);
fclose(f1); fclose(f2);
return 0;
}