Pagini recente » Cod sursa (job #1770531) | Cod sursa (job #3157789) | Cod sursa (job #1720232) | Cod sursa (job #241936) | Cod sursa (job #638331)
Cod sursa(job #638331)
#include <iostream>
#include <string.h>
#define i64 long long
#include <fstream>
using namespace std;
const i64 M1 = 100007;
const i64 M2 = 100021;
const i64 P = 1000001321;
const int nmax = 1024;
const i64 IM1 = 93829;
const i64 IM2 = 45939;
i64 P1[nmax], P2[nmax], A[nmax][nmax], H1[nmax], HI1[nmax], H2[nmax], HI2[nmax];
int N, M, Bun[nmax];
void calc()
{
P1[0] = P2[0] = 1;
int i;
for(i = 1; i <= (N >> 1); i++)
P1[i] = (P1[i - 1] * P) % M1,
P2[i] = (P2[i - 1] * P) % M2;
}
int Src()
{
int i;
int cat = 0, r = 0;
for(i = 1; i <= N; i++)
{
cat = cat * Bun[i] + Bun[i];
if(cat > r)
r = cat;
}
return r;
}
int main()
{
ifstream in ("dreptpal.in");
int i, j, k, Maxi;
i64 Rez;
in >> N >> M;
for(i = 1; i <= N; i++)
for(j = 1; j <= M; j++)
in >> A[i][j];
Maxi = N;
calc();
if(M & 1)
i = M;
else i = M - 1;
for(; i > 1; )
{
memset(H1, 0, sizeof(H1));
memset(H2, 0, sizeof(H2));
memset(HI1, 0, sizeof(HI1));
memset(HI2, 0, sizeof(HI2));
for(j = 1; j <= N; j++)
{
for(k = 1; k <= (i >> 1); k++)
{
H1[j] = (H1[j] * P + A[j][k]) % M1,
HI1[j] = (HI1[j] * P + A[j][i - k + 1]) % M1,
H2[j] = (H2[j] * P + A[j][k]) % M2,
HI2[j] = (HI2[j] * P + A[j][i - k + 1]) % M2;
}
if(H1[j] == HI1[j] && H2[j] == HI2[j])
Bun[j] = 1;
}
Rez = Src() * i;
if(Rez > Maxi)
Maxi = Rez;
memset(Bun, 0, sizeof(Bun));
for(j = 2; j + i - 1<= M; j++)
{
for(k = 1; k <= N; k++)
{
H1[k] = (((H1[k] - A[k][j - 1] * P1[(i >> 1) - 1]) % M1 * P) + A[k][j + (i >> 1) - 1]) % M1,
HI1[k] = ((HI1[k] - A[k][j + (i >> 1)]) * IM1 + A[k][j + i - 1] * P1[(i >> 1) - 1]) % M1,
H2[k] = (((H2[k] - A[k][j - 1] * P2[(i >> 1) - 1]) % M2 * P) + A[k][j + (i >> 1) - 1]) % M2,
HI2[k] = ((HI2[k] - A[k][j + (i >> 1)]) * IM2 + A[k][j + i - 1] * P2[(i >> 1) - 1]) % M2;
while(H1[k] < 0) H1[k] += M1;
while(HI1[k] < 0) HI1[k] += M1;
while(H2[k] < 0) H2[k] += M2;
while(HI2[k] < 0) HI2[k] += M2;
if(H1[k] == HI1[k] && H2[k] == HI2[k])
Bun[k] = 1;
}
Rez = Src() * i;
if(Rez > Maxi)
Maxi = Rez;
memset(Bun, 0, sizeof(Bun));
}
/*i >>= 1;
if(!(i & 1))i++;*/ i-=2;
}
ofstream out("dreptpal.out");
out << Maxi;
return 0;
}