Cod sursa(job #2302274)

Utilizator flibiaVisanu Cristian flibia Data 14 decembrie 2018 02:01:56
Problema DreptPal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#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]));
	}
}

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;
}