Cod sursa(job #2302369)

Utilizator lucametehauDart Monkey lucametehau Data 14 decembrie 2018 15:10:05
Problema DreptPal Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;

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

int n, m, sol;

int a[1005];
int v[1005][1005], lg[1005][1005];

void Manacher() {
  for(int i = 1; i <= n; i++) {
    int mid = 0;
    for(int j = 1; j <= m; j++) {
      if(j <= mid + lg[i][mid])
        lg[i][j] = min(lg[i][mid] + mid - j, lg[i][2 * mid - j]);
      while(j - lg[i][j] > 1 && j + lg[i][j] < m && v[i][j - lg[i][j] - 1] == v[i][j + lg[i][j] + 1])
        lg[i][j]++;
      if(j + lg[i][j] >= mid + lg[i][mid])
        mid = j;
    }
  }
}

void Skyline() {
  int st[1005], vf = 0;
  st[0] = 0;
  for(int i = 1; i <= n; i++) {
    while(vf && a[i] < a[st[vf]]) {
      sol = max(sol, (i - st[vf - 1] - 1) * a[st[vf]]);
      vf--;
    }
    st[++vf] = i;
  }
}

int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++)
      cin >> v[i][j];
  }
  Manacher();
  for(int j = 1; j <= m; j++) {
    for(int i = 1; i <= n; i++)
      a[i] = 2 * lg[i][j] + 1;
    Skyline();
  }
  cout << sol;
  return 0;
}