Pagini recente » Cod sursa (job #1152066) | Cod sursa (job #1859731) | Cod sursa (job #1933252) | Cod sursa (job #792802) | Cod sursa (job #2302275)
#include <bits/stdc++.h>
#define ll long long
#define MOD1 104053
#define MOD2 104059
#define P 137
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int n, m, sol[1010][1010], l[1010], r[1010], stk[1010], vf, mx;
ll a[1010][1010], pw1[1010], pw2[1010], hashL1[1010], hashL2[1010], hashR1[1010], hashR2[1010];
void solve(int x) {
for (int i = 1; i <= m; i++) {
hashL1[i] = (hashL1[i - 1] + a[x][i] * pw1[m - i + 1]) % MOD1;
hashL2[i] = (hashL2[i - 1] + a[x][i] * pw2[m - i + 1]) % MOD2;
}
for (int i = m; i > 0; i--) {
hashR1[i] = (hashR1[i + 1] + a[x][i] * pw1[i]) % MOD1;
hashR2[i] = (hashR2[i + 1] + a[x][i] * pw2[i]) % MOD2;
}
int st, dr, mid;
for (int y = 1; y <= m; y++) {
st = 1;
dr = min(y, m - y + 1);
while (st <= dr) {
mid = (st + dr) / 2;
int offsetL = y - mid;
int offsetR = m - (y + mid - 1);
ll hshL1 = ((hashL1[y] - hashL1[y - mid] + MOD1) * pw1[offsetL]) % MOD1;
ll hshL2 = ((hashL2[y] - hashL2[y - mid] + MOD2) * pw2[offsetL]) % MOD2;
ll hshR1 = ((hashR1[y] - hashR1[y + mid] + MOD1) * pw1[offsetR]) % MOD1;
ll hshR2 = ((hashR2[y] - hashR2[y + mid] + MOD2) * pw2[offsetR]) % MOD2;
if (hshL1 == hshR1 && hshL2 == hshR2)
st = mid + 1;
else dr = mid - 1;
}
sol[x][y] = 2 * dr - 1;
}
}
void solve2(int y) {
// vf = 0;
// for (int x = 1; x <= n; x++) {
// while (vf && sol[stk[vf]][y] > sol[x][y]) {
// int p = stk[vf--];
// mx = max(mx, sol[p][y] * (vf ? x - stk[vf] - 1 : x - 1));
// }
// stk[++vf] = x;
// }
// while (vf) {
// int p = stk[vf--];
// mx = max(mx, sol[p][y] * (vf ? m : m - stk[vf]));
// }
for (int x = 1; x <= n; x++) {
int st = x, dr = x;
while (st >= 1 && sol[st][y] >= sol[x][y])
st--;
st++;
while (dr <= n && sol[dr][y] >= sol[x][y])
dr++;
mx = max(mx, sol[x][y] * (dr - st));
}
}
int main() {
in >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
in >> a[i][j];
pw1[0] = pw2[0] = 1;
for (int i = 1; i <= 1000; i++) {
pw1[i] = (pw1[i - 1] * P) % MOD1;
pw2[i] = (pw2[i - 1] * P) % MOD2;
}
for (int i = 1; i <= n; i++)
solve(i);
for (int i = 1; i <= m; i++)
solve2(i);
out << mx;
return 0;
}