Cod sursa(job #636735)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 19 noiembrie 2011 22:59:48
Problema DreptPal Scor 90
Compilator cpp Status done
Runda .com 2011 Marime 1.47 kb
#include <fstream>
using namespace std;

const int NMAX = 1005;

int N, M, a[NMAX][NMAX];

int L[NMAX];
void work(int *s, int n)
{
	int lim = 1, mid = 1;
	L[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (i > lim)
		{
			lim = i;
			L[i] = 1;
			for (int l = i - 1, r = i + 1;l > 0 && r <= n && s[l] == s[r];--l, ++r)
				++L[i], lim = r;
		}
		else
		{
			L[i] = min(L[2*mid - i], lim - i + 1);
			if (i + L[i] - 1 == lim)
			{
				for (int l = i - L[i], r = i + L[i];l > 0 && r <= n && s[l] == s[r];--l, ++r)
					++L[i], lim = r;
			}
		}
		
		if (i + L[i] > mid + L[mid])
			mid = i;
	}
	
	for (int i = 1;i <= n;++i) s[i] = L[i]; 
}

int stk[NMAX], up[NMAX], down[NMAX];

void solve()
{
	int maxarea = 0;
	for (int j=1;j<=M;++j)
	{
		int z=0;
		stk[0] = 0; a[0][j] = 0;
		for (int i=1;i<=N;++i)
		{
			while (a[stk[z]][j] >= a[i][j]) -- z;
			up[i] = stk[z] + 1;
			stk[++z] = i;
		}
		stk[z=0] = 0; a[N+1][j] = 0;
		for (int i = N; i>=1; --i)
		{
			while (a[stk[z]][j] >= a[i][j]) --z;
			down[i] = stk[z] - 1;
			stk[++z] = i;
		}
		
		for (int i=1;i<=N;++i)
		{
			int height = down[i] - up[i] + 1;
			int area = (2*a[i][j] - 1)*height;
			maxarea = max(maxarea, area);
		}
	}
	
	ofstream fout("dreptpal.out");
	fout<<maxarea<<"\n";
}

int main()
{
	ifstream fin("dreptpal.in");
	fin>>N>>M;
	for (int i=1;i<=N;++i)
	{
		for (int j=1;j<=M;++j)
			fin>>a[i][j];
		work(a[i], M);
	}
	
	solve();
	
	return 0;
}