Cod sursa(job #1818398)

Utilizator antanaAntonia Boca antana Data 29 noiembrie 2016 10:37:00
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#define MAXN 1000

int n, m, man[MAXN+1][MAXN+1], v[MAXN+1][MAXN+1], left[MAXN+1][MAXN+1], right[MAXN+1][MAXN+1], st[MAXN+1];

inline int minim(int a, int b){
    return(a < b ? a : b);
}

void manacher(int lin)
{
    int c = 0, dr = 0, j;

    for(j=1; j<=m; ++j)
    {
        if(dr < j) man[lin][j] = 0;
        else man[lin][j] = minim(dr-j, man[lin][2*c-j]);

        while(j+man[lin][j]+1 <= m && j-man[lin][j]-1 > 0 && v[lin][j+man[lin][j]+1] == v[lin][j-man[lin][j]-1])
            man[lin][j]++;

        if(j + man[lin][j] > dr)
        {
            dr = j + man[lin][j];
            c = j;
        }
    }

    for(j=1; j<=m; ++j)
        man[lin][j] = man[lin][j] * 2 + 1;
}

int main()
{
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);

    int i, j, k = 0, ans = 0;

    scanf("%d%d", &n, &m);

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            scanf("%d", &v[i][j]);

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

    for(j=1; j<=m; ++j)
    {
        k = 0;
        st[++k] = left[1][j] = 1;

        for(i=2; i<=n; ++i){
            while(k > 0 && man[st[k]][j] >= man[i][j])
                left[i][j] += left[st[k--]][j];

            st[++k] = i;
            left[i][j]++;
        }

        k = 0;
        st[++k] = n;
        right[n][j] = 1;
        for(i=n-1; i>=1; --i){
            while(k > 0 && man[st[k]][j] >= man[i][j])
                right[i][j] += right[st[k--]][j];

            st[++k] = i;
            right[i][j]++;
        }
    }

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if((left[i][j] + right[i][j] - 1) * man[i][j] > ans)
                ans = (left[i][j] + right[i][j] - 1) * man[i][j];

    printf("%d", ans);

    return 0;
}