Cod sursa(job #2909463)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 13 iunie 2022 19:52:17
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.84 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];
short int maxl[MAX_N + 1], l[MAX_N + 1], r[MAX_N + 1];
int n, m;

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

int 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() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && maxl[i] <= maxl[st.top()]) {
            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] <= maxl[st.top()]) {
            st.pop();
        }
        if (!st.empty()) {
            r[i] = st.top();
        } else {
            r[i] = n + 1;
        }
        st.push(i);
    }
}

class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}

	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}

	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};

int main() {
    InParser 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 j = 1; j <= m; j++) {
        for (int i = 1; i <= n; i++) {
            maxl[i] = cb(i, j);
        }
        skyline();
        for (int i = 1; i <= n; i++) {
            answer = max(answer, (r[i] - l[i] - 1) * 1LL * maxl[i]);
        }
    }
    fout << answer;
    return 0;
}