Cod sursa(job #2798891)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 12 noiembrie 2021 00:47:29
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>

using namespace std;

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

const int INF = (int)1e5;

int solve(vector<int> &hist) {
  int maxArea = 0;
  hist.push_back(-INF);
  stack<int> st;
  for (int i = 0; i < (int)hist.size(); i++) {
    while ((int)st.size() > 0 && hist[st.top()] > hist[i]) {
      int l = st.top();
      st.pop();
      int area;
      if ((int)st.size() > 0)
        area = (i - st.top() - 1) * hist[l];
      else
        area = i * hist[l];
      maxArea = max(maxArea, area);
    }
    st.push(i);
  }
  return maxArea;
}

int main() {
  in.tie(NULL);
  out.tie(NULL);
  ios_base::sync_with_stdio(false);
  int n, m; in >> n >> m;
  vector<vector<int>> p;
  for (int i = 0; i < n; i++) {
    vector<int> s(m);
    for (int &x : s)
      in >> x;
    vector<int> pal(m);
    int l = -1, r = -1;
    for (int j = 0; j < m; j++) {
      if (j > r)
        pal[j] = 1;
      else
        pal[j] = min(pal[l + r - j], r - j + 1);
      while (j - pal[j] >= 0 && j + pal[j] < m && s[pal[j] + j] == s[j - pal[j]])
        pal[j]++;
      pal[j]--;
      if (j + pal[j] > r) {
        r = j + pal[j];
        l = j - pal[j];
      }
    }
    p.push_back(pal);
  }
  for (auto &row : p)
    for (int &x : row)
      x += x + 1;
  int ans = 1;
  for (int j = 0; j < m; j++) {
    vector<int> cand;
    for (int i = 0; i < n; i++)
      cand.push_back(p[i][j]);
    ans = max(ans, solve(cand));
  }
  out << ans << "\n";
  return 0;
}