Cod sursa(job #2456609)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 14 septembrie 2019 20:38:21
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("dreptpal.in");
ofstream g("dreptpal.out");

int a[1005][1005];
int z[1005][1005];
int stiva[1005];

void make_pal(int col, int m)
{
    int c = 0, r = 0;
    for (int i = 1; i <= m; ++ i)
    {
        int op = 2 * c - i;
        if (i > r || z[col][i] >= r - i)
        {
            if (i > r)
                r = i;
            int k = r + 1;
            while (a[col][k] == a[col][2 * i - k])
                k ++;
            k --;
            z[col][i] = k - i;
            if (k > r)
            {
                r = k;
                c = i;
            }
        }
        else
            z[col][i] = z[col][op];
        //cout << z[col][i] <<  " ";
    }
}
int main()
{
  int n, m;
  f >> n >> m;
  for (int i = 1; i <= n; ++ i)
  {
      for (int j = 1; j <= m; ++ j)
          f >> a[i][j];
      a[i][0] = -1;
     // cout << '\n';
      make_pal(i, n);
  }
  int ans = 0;
  for (int i = 2; i < m; ++ i)
  {
      int vf = 1;
      stiva[0] = 0;
      stiva[1] = 0;
      for (int j = 1; j <= m + 1; ++ j)
      {
          while (vf && z[i][j] < z[i][stiva[vf]])
          {
              ans = max(ans, (z[i][stiva[vf]] * 2 + 1) * (j - stiva[vf - 1] - 1));
              vf --;
          }
          stiva[ ++ vf] = j;
      }
  }
  g << ans;
}