Pagini recente » Cod sursa (job #1961305) | Cod sursa (job #468324) | Cod sursa (job #2943475) | Cod sursa (job #1142226) | Cod sursa (job #2909455)
#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];
int prefH[MAX_N + 1][MAX_N + 1], prefrevH[MAX_N + 1][MAX_N + 2], powerB[MAX_N + 1];
short int maxl[MAX_N + 1][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(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);
}
}
int 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) * 1LL * maxl[i][j]);
}
}
fout << answer;
return 0;
}