Cod sursa(job #1007328)

Utilizator cahemanCasian Patrascanu caheman Data 8 octombrie 2013 19:38:35
Problema DreptPal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<cstdio>

using namespace std;

int matrice[1025][1025], con[1025][1025], solutie[1025];

int min(int a, int b)
{
  if(a < b)
    return a;
  else
    return b;
}

int max(int a, int b)
{
  return a + b - min(a, b);
}

int main()
{
  freopen("dreptpal.in", "r", stdin);
  freopen("dreptpal.out", "w", stdout);
  int n, m, i, j, rez = 1, st, dr, indice, indice2;
  scanf("%d%d", &n, &m);
  for(i = 1; i <= n; ++ i)
    for(j = 1; j <= m; ++ j)
            scanf("%d", &matrice[i][j]);
  for(i = 1; i <= n; ++ i)
  {
    st = 1;
    dr = 1;
    for(j = 1; j <= m; ++ j)
    {
      if(j <= dr)
      {
        con[i][j] = min(con[i][st + dr - j], dr - j);
        if(j + con[i][j] >= dr)
        {
          dr = j + con[i][j];
          for(st = j - con[i][j];  st > 1 && dr < n && matrice[i][st - 1] == matrice[i][dr + 1]; -- st)
          {
            ++ con[i][j];
            ++ dr;
          }
        }
      }
      else
      {
        dr = j;
        for(st = j; st > 1 && dr < n && matrice[i][st - 1] == matrice[i][dr + 1]; -- st)
        {
          ++ dr;
          ++ con[i][j];
        }
      }
    }
    for(j = 1; j <= m; ++ j)
      con[i][j] = 1 + (con[i][j] + con[i][j]);
  }

  for(j = 1; j <= m; ++ j)
  {
    indice = 0;
    for(i = 1; i <= n; ++ i)
    {
      for(indice2 = solutie[indice]; indice && con[i][j] < con[solutie[indice]][j]; -- indice)
        rez = max(rez, con[solutie[indice]][j] * (indice2 - solutie[indice - 1]));
      solutie[++ indice] = i;
    }
    for(indice2 = solutie[indice]; indice; -- indice)
    {
      rez = max(rez, con[solutie[indice]][j] * (indice2 - solutie[indice - 1]));
    }
  }
  printf("%d", rez);
  return 0;
}