Cod sursa(job #2960442)

Utilizator ezluciPirtac Eduard ezluci Data 4 ianuarie 2023 13:49:31
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "dreptpal";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 1e3;
const int mMAX = 1e3;

int n, m;
int mat[nMAX + 1][mMAX + 1];
int rz[nMAX + 1][mMAX + 1];
int st[nMAX + 1];
int dr[nMAX + 1];


int main()
{
   fin >> n >> m;
   for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
         fin >> mat[i][j];
   
   for (int i = 1; i <= n; ++i, cout << '\n')
   {
      int l = 1, r = 1;

      rz[i][1] = 0;
      for (int j = 2; j <= m; ++j)
      {
         if (r < j)
            rz[i][j] = 0;
         else
            rz[i][j] = min(rz[i][l+r-j], r-j);
         
         while (j - rz[i][j] - 1 >= 1 && j + rz[i][j] + 1 <= m
               && mat[i][j - rz[i][j] - 1] == mat[i][j + rz[i][j] + 1])
            rz[i][j]++;
         
         if (j + rz[i][j] > r)
            l = j - rz[i][j],
            r = j + rz[i][j];
      }
   }

   int ARIEMAX = 0;

   for (int j = 1; j <= m; ++j)
   {
      stack<int> stiv;
      
      for (int i = 1; i <= n; ++i)
      {
         while (!stiv.empty() && rz[stiv.top()][j] >= rz[i][j])
            stiv.pop();
         
         if (stiv.empty())
            st[i] = 0;
         else
            st[i] = stiv.top();
         
         stiv.push(i);
      }

      while (!stiv.empty())
         stiv.pop();
      
      for (int i = n; i >= 1; --i)
      {
         while (!stiv.empty() && rz[stiv.top()][j] >= rz[i][j])
            stiv.pop();
         
         if (stiv.empty())
            dr[i] = n+1;
         else
            dr[i] = stiv.top();
         
         stiv.push(i);
      }

      for (int i = 1; i <= n; ++i)
         ARIEMAX = max(ARIEMAX, (dr[i]-st[i]-1) * (2*rz[i][j] + 1));
   }

   fout << ARIEMAX;
}