Cod sursa(job #1661454)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 23 martie 2016 21:24:54
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>

using namespace std;

const int N = 1010;

int A[N][N];
int P[N][N];
int jump[N];
int latura[N];

void Manacher(int n, int m) {
    int i, j, l, r;

    for(i = 1; i <= n; ++ i) {

        l = 0;
        r = 0;

        for(j = 1; j <= m; ++ j) {

            if(j <= r)
                P[i][j] = min(P[i][2 * l - j], r - j);

            while(j - P[i][j] > 1 && j + P[i][j] < m && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
                ++ P[i][j];

            if(j + P[i][j] > r) {
                r = j + P[i][j];
                l = j;
            }

        }
    }
}

int main() {
    ifstream cin("dreptpal.in");
    ofstream cout("dreptpal.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m;
    int i, j;
    int k, ret;

    cin >> n >> m;

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= m; ++ j)
            cin >> A[i][j];

    Manacher(n, m);

    ret = 0;

    for(j = 1; j <= m; ++ j) {

        for(i = 1; i <= n; ++ i) {

            k = i - 1;

            while(k >= 1 && P[k][j] >= P[i][j])
                k = jump[k];

            jump[i] = k;

            latura[i] = i - k;
        }

        for(i = n; i >= 1; -- i) {

            k = i + 1;

            while(k <= n && P[k][j] >= P[i][j])
                k = jump[k];

            jump[i] = k;

            latura[i] += k - i;
        }

        for(i = 1; i <= n; ++ i)
            ret = max((latura[i] - 1) * (2 * P[i][j] + 1), ret);
    }

    cout << ret << '\n';

    return 0;
}