Cod sursa(job #2037088)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 11 octombrie 2017 18:26:29
Problema DreptPal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

bool is_good(int i, int cnt, int m) {
  return i + cnt <= m and i - cnt >= 1;
}

void fill_pali(vector < int > &pali, vector < int > &v, int m) {

  int poz = -1;
  int max_r = -1;
  for (int i = 1; i <= m; i ++) {
    int cnt = 0;
    if (i >= max_r) {
      while (is_good(i, cnt, m)) {
        if (v[i + cnt] == v[i - cnt]) {
          cnt ++;
          continue;
        }
        break;
      }

      cnt --;
      pali[i] = cnt * 2 + 1;
      poz = i;
      max_r = i + cnt;
      continue;
    }

    int k = pali[2 * poz - i];
    if (i + k < max_r) {
      pali[i] = k;
      continue;
    }

    cnt = max_r - i + 1;
    while (is_good(i, cnt, m)) {
      if (v[i + cnt] == v[i - cnt]) {
        cnt ++;
        continue;
      }
      break;
    }

    cnt --;
    pali[i] = cnt * 2 + 1;
    poz = i;
    max_r = i + cnt;
  }
}

int main(int argc, char const *argv[]) {
  
  int n, m;
  cin >> n >> m;

  vector < vector < int > > mat(n + 1, vector < int > (m + 7));
  for (int i = 1 ; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
      cin >> mat[i][j];
    }
  }

  vector < vector < int > > pali(n + 7, vector < int > (m + 7));
  for (int i = 1; i <= n; i ++) {
    fill_pali(pali[i], mat[i], m);
  }

  stack < int > st;
  vector < vector < int > > up(n + 7, vector < int > (m + 7));
  vector < vector < int > > dw(n + 7, vector < int > (m + 7));

  for (int j = 1; j <= m; j ++) {
    pali[0][j] = -1;
    pali[n + 1][j] = -1;

    st.push(0);
    for (int i = 1; i <= n; i ++) {
      if (pali[st.top()][j] >= pali[i][j]) {
        while (pali[st.top()][j] >= pali[i][j]) {
          st.pop();
        }
        up[i][j] = st.top() + 1;
        st.push(i);
      }
      else {
        up[i][j] = i;
        st.push(i);
      }
    }

    while (!st.empty()) {
      st.pop();
    }
    st.push(n + 1);
    for (int i = n; i >= 1; i --) {
      if (pali[st.top()][j] >= pali[i][j]) {
        while (pali[st.top()][j] >= pali[i][j]) {
          st.pop();
        }
        dw[i][j] = st.top() - 1;
        st.push(i);
      }
      else {
        dw[i][j] = i;
        st.push(i);
      }
    }

    while (!st.empty()) {
      st.pop();
    }  
  }

  int sol = 0;
  for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
      int cur = pali[i][j] * (dw[i][j] - up[i][j] + 1);
      sol = max(sol, cur);
    }
  }

  cout << sol << '\n'; 
}