Cod sursa(job #637803)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 20 noiembrie 2011 16:46:43
Problema DreptPal Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 2.91 kb
#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 = 1000000021;
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();

    int Li = 1, ok;
    int Ls = M;
    while(Li + 2 <= Ls)
    {
        i = (Li + Ls) >> 1;
        if(!(i & 1))
            i++;
        memset(H1, 0, sizeof(H1));
        memset(H2, 0, sizeof(H2));
        memset(HI1, 0, sizeof(HI1));
        memset(HI2, 0, sizeof(HI2));
        ok = 0;
        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, ok = 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, ok = 1;
            }


            Rez = Src() * i;
            if(Rez > Maxi)
                Maxi = Rez;
            memset(Bun, 0, sizeof(Bun));
        }
        if(ok == 1)
            Li = i;
        else Ls = i - 1;
    }

    ofstream out("dreptpal.out");
    out << Maxi;
    return 0;
}