Cod sursa(job #637358)

Utilizator VmanDuta Vlad Vman Data 20 noiembrie 2011 14:00:13
Problema DreptPal Scor 10
Compilator cpp Status done
Runda .com 2011 Marime 2.01 kb
#include <cstdio>

#define Nmax 1001
#define Mmax 1001

int N, M, i, j, st;
int A[Nmax][Mmax], L[Nmax][Nmax];
int A1[Nmax], A2[Nmax], S[Nmax];
int best;

int palind(int x, int y)
{
    int st, dr;

    st = dr = y;
    while (st>0 && dr<M)
    {
          --st; ++dr;
          if (A[x][st] != A[y][st]) break;
    }
    
    return dr-st-1;
}

int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    
    scanf("%d %d", &N, &M);
    for (i=0; i<N; ++i)
        for (j=0; j<M; ++j)
            scanf("%d", &A[i][j]);
            
    for (i=0; i<M; ++i)
        {
              for (j=0; j<N; ++j)
              {
                  L[i][j] = palind(i, j);
                  if (L[i][j] > best) best = L[i][j];
              }

              //stanga
              S[st=0] = 0;
              A1[0] = L[0][i];
              for (j=0; j<N; ++j)
              {
                  while (L[S[st]][i] > L[j][i] && st>=0)
                  {
                        if (L[j][i] * (j - S[st] + 1) > A1[j]) A1[j] = L[j][i] * (j - S[st] + 1);
                        --st;
                  }
                  if (st>=0 && L[j][i] * (j - S[st] + 1) > A1[j]) A1[j] = L[j][i] * (j - S[st] + 1);
                  S[++st] = j;
              }
              //dreapta
              S[st=0] = N-1;
              A2[N-1] = L[N-1][i];
              for (j=N-1; j>=0; --j)
              {
                  while (L[S[st]][i] > L[j][i] && st>=0)
                  {
                        if (L[j][i] * (S[st] - j + 1) > A2[j]) A2[j] = L[j][i] * (S[st] - j + 1);
                        --st;
                  }
                  if (st>=0 && L[j][i] * (S[st] - j + 1) > A2[j]) A2[j] = L[j][i] * (j - S[st] + 1);
                  S[++st] = j;                  
              }
              //total
              for (j=0; j<N; ++j)
                  if (A1[j] + A2[j] > best) best = A1[j] + A2[j];
        }
    
    printf("%d\n", best);
    
    return 0;
}