Cod sursa(job #2044524)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 21 octombrie 2017 10:51:49
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_N = 1000;

int q[2 * MAX_N + 5];

int m[MAX_N + 5][2 * MAX_N + 5];
int t[MAX_N + 5][MAX_N + 5];
int st[MAX_N + 5];
int left[MAX_N + 5];
int right[MAX_N + 5];

int solve(int ind, int n) {
  int mid = 1, R = 1;

  for (int i = 1; i <= n; ++i)
    scanf("%d", &q[2 * i - 1]);

  for (int i = 1; i <= 2 * n; ++i) {
    int sim = mid - (i - mid);
    int dif = m[ind][sim];
    if (i > R) {
      int l = i;
      int r = i;
      while (l > 0 && r <= 2 * n && q[l] == q[r]) {
        m[ind][i]++;
        l--;
        r++;
      }
      l++;
      r--;
      R = r;
      mid = i;
    } else if (i + dif >= R) {
      int l = i - (R - i);
      int r = R;
      m[ind][i] = R - i;
      while (l > 0 && r <= 2 * n && q[l] == q[r]) {
        m[ind][i]++;
        l--;
        r++;
      }
      l++;
      r--;
      R = r;
      mid = i;
    } else {
      m[ind][i] = dif;
    }
  }
  for (int i = 1; i <= n; ++i)
    t[ind][i] = (m[ind][2 * i - 1] + 1) / 2;
}
int main() {
  freopen("dreptpal.in", "r", stdin);
  freopen("dreptpal.out", "w", stdout);

  int N, M;
  scanf("%d%d ", &N, &M);
  for (int i = 1; i <= N; ++i)
    solve(i, M);

  int ans = 0;
  for (int j = 1; j <= M; ++j) {
    int top = 0;
    st[0] = 0;
    for (int i = 1; i <= N; ++i) {
      while (top > 0 && t[st[top]][j] >= t[i][j])
        top--;
      st[++top] = i;
      left[i] = st[top - 1] + 1;
    }
    top = 0;
    st[0] = N + 1;
    for (int i = N; i >= 1; --i) {
      while (top > 0 && t[st[top]][j] >= t[i][j])
        top--;
      st[++top] = i;
      right[i] = st[top - 1] - 1;
    }
    for (int i = 1; i <= N; ++i)
      ans = max(ans, (2 * (t[i][j] - 1) + 1) * (right[i] - left[i] + 1));
  }

  printf("%d\n", ans);

  return 0;
}