Cod sursa(job #865040)

Utilizator visanrVisan Radu visanr Data 25 ianuarie 2013 23:05:19
Problema DreptPal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <cstdlib>
#include <stack>
#include <algorithm>
using namespace std;

#define Nmax 1010
#define Inf 0x3f3f3f3f

int N, M, A[Nmax][Nmax], Pal[Nmax][Nmax];
int i, j, Up[Nmax], Down[Nmax];
int C, R, Ans;

int main()
{
    freopen("dreptpal.in", "r", stdin);
    freopen("dreptpal.out", "w", stdout);
    scanf("%i %i", &N, &M);
    for(i = 1; i <= N; i++)
        for(j = 1; j <= M; j++)
            scanf("%i", &A[i][j]);
    for(i = 1; i <= N; i++)
    {
        R = C = 0;
        for(j = 1; j <= M; j++)
        {
            Pal[i][j] = Pal[i][2 * C - j];
            while(j - Pal[i][j] >= 1 && j + Pal[i][j] <= M && A[i][j - Pal[i][j]] == A[i][j + Pal[i][j]]) Pal[i][j] ++;
            Pal[i][j] --;
            if(j + Pal[i][j] > R)
            {
                R = Pal[i][j];
                C = j;
            }
        }
        for(j = 1; j <= M; j++) Pal[i][j] = 2 * Pal[i][j] + 1;
    }
    for(j = 1; j <= M; j++)
    {
        stack<int> S;
        S.push(0);
        Pal[0][j] = Pal[N + 1][j] = -Inf;
        for(i = 1; i <= N; i++)
        {
            while(!S.empty() && Pal[i][j] <= Pal[S.top()][j]) S.pop();
            Up[i] = S.top() + 1;
            S.push(i);
        }
        while(!S.empty()) S.pop();
        S.push(N + 1);
        for(i = N; i; i--)
        {
            while(!S.empty() && Pal[i][j] <= Pal[S.top()][j]) S.pop();
            Down[i] = S.top() - 1;
            S.push(i);
        }
        for(i = 1; i <= N; i++)
            Ans = max(Ans, Pal[i][j] * (Down[i] - Up[i] + 1));
    }
    printf("%i\n", Ans);
    return 0;
}