Cod sursa(job #2748387)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 30 aprilie 2021 12:36:59
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>

const int NMAX = 1e3;

int a[1 + NMAX];

int manacher[1 + NMAX][1 + NMAX];

int next_left[1 + NMAX][1 + NMAX];
int next_right[1 + NMAX][1 + NMAX];
std::vector<int> stack;

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

  int n, m;
  in >> n >> m;

  for (int line = 1; line <= n; ++line) {
    for (int i = 1; i <= m; ++i)
      in >> a[i];

    manacher[line][1] = 1;

    int curr = 1;
    int best_right = 1;

    for (int i = 2; i <= m; ++i) {
      int len = 1;

      if (i <= best_right)
        len = std::min(manacher[line][2 * curr - i], best_right - i + 1);
      while (i - len >= 1 && i + len - 1 <= m && a[i + len] == a[i - len]) ++len;

      if (i + len - 1 > best_right) {
        best_right = i + len - 1;
        curr = i;
      }

      manacher[line][i] = len;
    }
  }

  stack.reserve(n);

  for (int col = 1; col <= m; ++col) {
    for (int i = 1; i <= n; ++i) {
      while (!stack.empty() && manacher[stack.back()][col] >= manacher[i][col])
        stack.pop_back();

      next_left[i][col] = stack.empty() ? 0 : stack.back();
      stack.push_back(i);
    }
    stack.clear();

    for (int i = n; i >= 1; --i) {
      while (!stack.empty() && manacher[stack.back()][col] >= manacher[i][col])
        stack.pop_back();

      next_right[i][col] = stack.empty() ? (n + 1) : stack.back();
      stack.push_back(i);
    }
    stack.clear();
  }

  int ans = 0;
  for (int line = 1; line <= n; ++line) {
    for (int i = 1; i <= m; ++i)
      ans = std::max(ans, (2 * manacher[line][i] - 1) * (next_right[line][i] - next_left[line][i] - 1));
  }

  out << ans << '\n';

  return 0;
}