Cod sursa(job #2909466)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 13 iunie 2022 19:54:18
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <fstream>
#include <stack>

using namespace std;

const int MAX_N = 1e3;
const int B = 257;
const int P = 1e9 + 7;
int a[MAX_N + 1][MAX_N + 1];
long long prefH[MAX_N + 1][MAX_N + 1], prefrevH[MAX_N + 1][MAX_N + 2], powerB[MAX_N + 1];
int maxl[MAX_N + 1][MAX_N + 1];
long long l[MAX_N + 1], r[MAX_N + 1];
int n, m;

long long rangeHash(int lin, int l, int r) {
    return (prefH[lin][r] - prefH[lin][l - 1] * 1LL * powerB[r - l + 1] % P + P) % P;
}

long long rangerevHash(int lin, int l, int r) {
    return (prefrevH[lin][l] - prefrevH[lin][r + 1] * 1LL * powerB[r - l + 1] % P + P) % P;
}

bool check(int lin, int l, int r) {
    return l >= 1 && l <= m && r >= 1 && r <= m && rangeHash(lin, l, r) == rangerevHash(lin, l, r);
}

int cb_par(int lin, int centru) {
    int st = 1, dr = m / 2, sol = -1;
    while (st <= dr) {
        int mijl = (st + dr) / 2;
        if (check(lin, centru - mijl + 1, centru + mijl)) {
            sol = mijl;
            st = mijl + 1;
        } else {
            dr = mijl - 1;
        }
    }
    return 2 * sol;
}

int cb_imp(int lin, int centru) {
    int st = 0, dr = (m + 1) / 2, sol = -1;
    while (st <= dr) {
        int mijl = (st + dr) / 2;
        if (check(lin, centru - mijl, centru + mijl)) {
            sol = mijl;
            st = mijl + 1;
        } else {
            dr = mijl - 1;
        }
    }
    return 2 * sol + 1;
}

int cb(int lin, int pos) {
    return max(cb_par(lin, pos), cb_imp(lin, pos));
}

void skyline(int col) {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && maxl[i][col] <= maxl[st.top()][col]) {
            st.pop();
        }
        if (!st.empty()) {
            l[i] = st.top();
        } else {
            l[i] = 0;
        }
        st.push(i);
    }
    while (!st.empty()) {
        st.pop();
    }
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && maxl[i][col] <= maxl[st.top()][col]) {
            st.pop();
        }
        if (!st.empty()) {
            r[i] = st.top();
        } else {
            r[i] = n + 1;
        }
        st.push(i);
    }
}

signed main() {
    ifstream fin("dreptpal.in");
    ofstream fout("dreptpal.out");
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            fin >> a[i][j];
            prefH[i][j] = (prefH[i][j - 1] * 1LL * B % P + a[i][j]) % P;
        }
        for (int j = m; j >= 1; j--) {
            prefrevH[i][j] = (prefrevH[i][j + 1] * 1LL * B % P + a[i][j]) % P;
        }
    }
    powerB[0] = 1;
    for (int i = 1; i <= m; i++) {
        powerB[i] = powerB[i - 1] * 1LL * B % P;
    }
    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            maxl[i][j] = cb(i, j);
        }
    }
    for (int j = 1; j <= m; j++) {
        skyline(j);
        for (int i = 1; i <= n; i++) {
            answer = max(answer, (r[i] - l[i] - 1) * maxl[i][j]);
        }
    }
    fout << answer;
    return 0;
}