Cod sursa(job #2314753)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 9 ianuarie 2019 00:22:30
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
# include <fstream>

#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

using namespace std;

ifstream fin ("dreptpal.in");
ofstream fout ("dreptpal.out");

int n, m, i, j, v[1010], s[1010], a[1010][1010], d[1010][1010], x, c, mid, z, dr;

int main () {
	fin >> n >> m;
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			fin >> a[i][j];
		}
	}
	for (i = 1; i <= n; ++i) {
		d[i][1] = 1;
		z = 1;
		mid = 1;
		for (j = 2; j <= m; ++j) {
			c = 0;
			if (z <= j) {
				d[i][j] = 1;
			} else {
				d[i][j] = min(d[i][mid - (j - mid)], 2 * (z - j) + 1);
				c = d[i][j] / 2;
			}
			while (j - (c + 1) > 0 && j + (c + 1) <= m && a[i][j - (c + 1)] == a[i][j + (c + 1)]) {
				c++;
				d[i][j] += 2;
			}
			if (j + c > z) {
				z = j + c;
				mid = j;
			}
		}
	}
	for (j = 1; j <= m; ++j) {
		s[0] = 0;
		dr = 0;
		for (i = 1; i <= n; ++i) {
			while (dr > 0 && d[i][j] <= d[ s[dr] ][j]) {
                dr--;
			}
			v[i] = s[dr];
			s[++dr] = i;
		}
		s[0] = n + 1;
		dr = 0;
		for (i = n; i > 0; --i) {
			while (dr > 0 && d[i][j] <= d[ s[dr] ][j]) {
                dr--;
			}
			x = max(x, (s[dr] - v[i] - 1) * d[i][j]);
			s[++dr]=i;
		}
	}
	fout << x;
	return 0;
}