Cod sursa(job #1003627)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 1 octombrie 2013 08:56:38
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>

#define LL long long
#define NMAX 1007

using namespace std;

int D[NMAX][NMAX], Last, Nr, n, m, a[NMAX][NMAX], Mat[NMAX][NMAX];
stack < int > Stiva;

void Manacher(int Lung, int A[], int Ind){
    for(int i = 1; i <= Lung; ++ i){
        if(i == 1){
            D[Ind][i] = 1;
            Last = 1;
        }
        else
            D[Ind][i] = max(min(D[Ind][Last - (i - Last)] - 1, Last + D[Ind][Last] - i), 1);
        int St = i - D[Ind][i], Dr = i + D[Ind][i];
        while(St >= 1 && Dr <= Lung && A[St] == A[Dr]){
            ++ D[Ind][i];
            -- St;
            ++ Dr;
        }
        if(i + D[Ind][i] > Last + D[Ind][Last])
            Last = i;
    }
}

int main(){
    int Dr, Maxim = -1;
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= m; ++ j)
            scanf("%d", &a[i][j]);
        Manacher(m, a[i], i);
    }
    /**for(int i = 1; i <= n; ++ i, printf("\n"))
        for(int j = 1; j <= m; ++ j)
            printf("%d ", D[i][j]);**/
    for(int i = 1; i <= m; ++ i){
        while(! Stiva.empty())
            Stiva.pop();
        for(int j = 1; j <= n; ++ j){
            while(! Stiva.empty())
                if(D[Stiva.top()][i] >= D[j][i])
                    Stiva.pop();
                else
                    break;
            if(Stiva.empty())
                Dr = 0;
            else
                Dr = Stiva.top();
            Stiva.push(j);
            Mat[j][i] = (j - Dr) * ((D[j][i] * 2) - 1);
        }
        while(! Stiva.empty())
            Stiva.pop();
        for(int j = n; j >= 1; -- j){
            while(! Stiva.empty())
                if(D[Stiva.top()][i] >= D[j][i])
                    Stiva.pop();
                else
                    break;
            if(Stiva.empty())
                Dr = n + 1;
            else
                Dr = Stiva.top();
            Stiva.push(j);
            Maxim = max(Maxim, (Dr - j - 1) * (D[j][i] * 2 - 1) + Mat[j][i]);
        }
    }
    printf("%d", Maxim);
    return 0;
}