Pagini recente » Cod sursa (job #1026990) | Cod sursa (job #795563) | Cod sursa (job #758828) | Cod sursa (job #1333358) | Cod sursa (job #2044189)
#include <cstdio>
const int MAX_N = 1000;
int matr[MAX_N][MAX_N];
int pal[MAX_N][MAX_N];
void manacher(int *v, int *d, int n) {
int st, dr, cent;
st = dr = cent = 0;
for(int i = 1; i < n; ++i) {
if(i > dr)
st = cent = dr = i;
else {
d[i] = d[2 * cent - i];
if(i + d[i] >= dr) {
d[i] = dr - i;
cent = i;
st = cent - d[i];
}
}
while(st - 1 >= 0 && dr + 1 < n && v[st - 1] == v[dr + 1]) {
++d[cent];
--st;
++dr;
}
}
}
int rez;
int top;
int st[MAX_N];
int w[MAX_N];
void baga(int x) {
int h = 0;
while(top > 0 && x <= st[top - 1]) {
h += w[top - 1];
if(h * st[top - 1] > rez)
rez = h * st[top - 1];
--top;
}
st[top] = x;
w[top++] = h + 1;
}
int main() {
int n, m;
FILE *fin = fopen("dreptpal.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(int l = 0; l < n; ++l) {
for(int c = 0; c < m; ++c)
fscanf(fin, "%d", &matr[l][c]);
manacher(matr[l], pal[l], m);
}
fclose(fin);
for(int c = 0; c < m; ++c) {
top = 0;
for(int l = 0; l < n; ++l)
baga(2 * pal[l][c] + 1);
baga(0);
}
FILE *fout = fopen("dreptpal.out", "w");
fprintf(fout, "%d", rez);
fclose(fout);
return 0;
}