Cod sursa(job #2693379)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 5 ianuarie 2021 17:56:38
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>

using namespace std;

const int NMAX = 1000;
const int MMAX = 1000;

int n, m;

int x[1 + NMAX][1 + MMAX];

int lung[1 + NMAX][1 + MMAX];

int stSize;
int st[1 + NMAX];

int sus[1 + NMAX];
int jos[1 + NMAX];

void extindere(int linie, int index)
{
  while (1 <= index - lung[linie][index] && index + lung[linie][index] <= m && x[linie][index - lung[linie][index]] == x[linie][index + lung[linie][index]])
  {
    lung[linie][index]++;
  }
  lung[linie][index]--;
}

int main()
{
  ifstream in("dreptpal.in");
  ofstream out("dreptpal.out");

  in >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
    {
      in >> x[i][j];
    }
  }

  // Manacher
  for (int i = 1; i <= n; i++)
  {
    int pozPal = 0;

    for (int j = 1; j <= m; j++)
    {
      if (pozPal + lung[i][pozPal] >= j)
      {
        int sim = pozPal - (j - pozPal);

        if (sim - lung[i][sim] > pozPal - lung[i][pozPal])
        {
          lung[i][j] = lung[i][sim];
        }
        else
        {
          lung[i][j] = pozPal + lung[i][pozPal] - j;
          extindere(i, j);
        }
      }
      else
      {
        extindere(i, j);
      }

      if (j + lung[i][j] > pozPal + lung[i][pozPal])
      {
        pozPal = j;
      }
    }
  }

  int sol = 0;

  for (int j = 1; j <= m; j++)
  {
    // Limita sus
    stSize = 1;
    st[0] = 0;
    for (int i = 1; i <= n; i++)
    {
      while (stSize >= 0 && lung[st[stSize]][j] >= lung[i][j])
        stSize--;

      sus[i] = st[stSize] + 1;

      stSize++;
      st[stSize] = i;
    }

    // Limita jos
    stSize = 1;
    st[0] = n + 1;
    for (int i = n; i >= 1; i--)
    {
      while (stSize >= 0 && lung[st[stSize]][j] >= lung[i][j])
        stSize--;

      jos[i] = st[stSize] - 1;

      stSize++;
      st[stSize] = i;
    }

    // Sol
    for (int i = 1; i <= n; ++i)
    {
      sol = max(sol, (jos[i] - sus[i] + 1) * (2 * lung[i][j] + 1));
    }
  }

  out << sol << '\n';

  return 0;
}