Cod sursa(job #2009582)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 10 august 2017 01:05:08
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("dreptpal.in");
ofstream fo("dreptpal.out");

const int N = 1024;

int pal[N][N], mx[N][N], st[N], dr[N], v[N];

int n, m;

void manacher(int pal[N], int str[N]) {
	for (int i = 1, l = -1, r = -1; i <= m; ++i) {
		if (i >= r) {
			for (l = r = i; str[r + 1] == str[l - (r - l) - 1]; ++r);
			pal[l] = r - l + 1; }
		else if (i + pal[l - (i - l)] < r) {
			pal[i] = pal[l - (i - l)]; }
		else {
			for (l = i; str[r + 1] == str[l - (r - l) - 1]; ++r);
			pal[l] = r - l + 1; } } }


int main() {
	vector<int> stk;
	int ant(1);

	fi >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			fi >> mx[i][j]; 
		mx[i][0] = -1;
		mx[i][m + 1] = -2; }

	for (int i = 1; i <= n; ++i)
		manacher(pal[i], mx[i]);

	v[0] = -2;
	v[n + 1] = -3;

	for (int j = 1; j <= m; ++j) {
		for (int i = 1; i <= n; ++i)
			v[i] = pal[i][j];

		stk.push_back(0);
		for (int i = 1; i <= n; ++i) {
			while (v[stk.back()] >= v[i])
				stk.pop_back();
			st[i] = stk.back() + 1;
			stk.push_back(i); }
		stk.clear();

		stk.push_back(n + 1);
		for (int i = n; i >= 1; --i) {
			while (v[stk.back()] >= v[i])
				stk.pop_back();
			dr[i] = stk.back() - 1; 
			stk.push_back(i); } 
		stk.clear();

		for (int i = 1; i <= n; ++i)
			ant = max(ant, (dr[i] - st[i] + 1) * (2 * v[i] - 1)); }

	fo << ant << endl;

	return 0; }