Cod sursa(job #637508)

Utilizator VmanDuta Vlad Vman Data 20 noiembrie 2011 14:56:04
Problema DreptPal Scor 50
Compilator cpp Status done
Runda .com 2011 Marime 2.36 kb
#include <cstdio>

#define Nmax 1001

int N, M, i, j, st;
short int A[Nmax][Nmax];
short int L[Nmax][Nmax];
int A1[Nmax], A2[Nmax], S[Nmax];
int best;
char SS[10000];

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

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

void solve()
{
         int p = 0;
              for (j=0; j<N; ++j)
              {
                  L[i][j] = palind(i, j);
                  if (L[i][j] > best) best = L[i][j];
                  p += L[i][j];
              }
              if (p < best) return;

              //stanga
              for (j=0; j<N; ++j)
              {
                  A1[j] = L[i][0];                  
                  while (L[i][S[st]] >= L[i][j] && st>=0)
                        --st;
                  if (st>=0 && L[i][j] * (j - S[st]) > A1[j]) A1[j] = L[i][j] * (j - S[st]);
                  else if (st<0 && L[i][j] * (j + 1) > A1[j]) A1[j] = L[i][j] * (j + 1);
                  S[++st] = j;
              }
              //dreapta
              for (j=N-1; j>=0; --j)
              {
                  A2[j] = L[i][j];
                  while (L[i][S[st]] >= L[i][j] && st>=0)
                        --st;
                  if (st>=0 && L[i][j] * (S[st] - j) > A2[j]) A2[j] = L[i][j] * (S[st] - j);
                  else if (st<0 && L[i][j] * (N - j) > A2[j]) A2[j] = L[i][j] * (N - j);                  
                  S[++st] = j;                                                    
                  
                  //total
                  if (A1[j] + A2[j] - L[i][j] > best) best = A1[j] + A2[j] - L[i][j];
              }
                          
}

int main()
{
    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
    
    scanf("%d %d\n", &N, &M);
    for (i=0; i<N; ++i)
    {
        fgets(SS, 10000, stdin);
        int k=0;
        for (j=0; j<M; ++j)
        {
            while ('0' <= SS[k] && SS[k] <= '9')
            {
             A[i][j] = (A[i][j] * 10) + SS[k] - '0';
             ++k;
            }            
            ++k;
        }
    }
    
    if (N*M > 100000) best = 100;
    for (i=0; i<M; ++i)
        solve();
    
    printf("%d\n", best);
    
    return 0;
}