Cod sursa(job #2388103)

Utilizator shantih1Alex S Hill shantih1 Data 25 martie 2019 17:47:05
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <queue>
#define fi first
#define se second

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

const int nmx=1005;
int n,i,j,c,r,nr,m,rez;
int v[nmx][nmx],l[nmx][nmx],st[nmx],dr[nmx];

typedef pair<int,int> per;
per p;
deque<per> dq;

int main() {
	
	fin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
	  		fin>>v[i][j];
	
	for(i=1;i<=n;i++)
	{
		v[i][0]=-1;
		v[i][m+1]=-2;
		c=1;
		r=1;
		for(j=1;j<=m;j++)
		{
			if(j<=r)
				l[i][j]=min(r-j, l[i][2*c-j]);
			
			while(v[i][j+l[i][j]]==v[i][j-l[i][j]])
				l[i][j]++;
			l[i][j]--;
			
			if(j+l[i][j]>r)
				c=j, r=j+l[i][j];
		}
	}
	
	for(j=1;j<=m;j++)
	{
		dq.push_back({l[1][j], 1});
		st[1]=1;
		for(i=2;i<=n;i++)
		{
			p={l[i][j], i};
			while(!dq.empty() && p.fi<=dq.back().fi)
				dq.pop_back();
						
			if(dq.empty())	st[i]=i;
			else	st[i]=i-dq.back().se;
			dq.push_back(p);
		}
		while(!dq.empty())	dq.pop_back();
		
		dq.push_back({l[n][j], n});
		dr[n]=1;
		for(i=n-1;i>=1;i--)
		{
			p={l[i][j], i};
			while(!dq.empty() && p.fi<=dq.back().fi)
				dq.pop_back();
			
			if(dq.empty())	dr[i]=n-i+1;
			else	dr[i]=dq.back().se-i;
			dq.push_back(p);
		}
		while(!dq.empty())	dq.pop_back();
		
		for(i=1;i<=n;i++)
			rez=max(rez, (st[i]+dr[i]-1)*(2*l[i][j]+1));
	}
	
	fout<<rez<<"\n";
}