Cod sursa(job #2680728)

Utilizator BogdanTicuTicu Bogdan Valeriu BogdanTicu Data 4 decembrie 2020 01:05:54
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

int mat[1005][1005],z[1005][1005];
int st[1005];
void manacher(int col,int n)
{
	int C=0,R=0;
	for(int i=1;i<=n;i++)
	{
		int aux=2*C-i;
		if(i>R||z[col][aux]>=R-i)
		{
			if(i>R) R=i;
			int k=R;
			while(k<=n && mat[col][k]==mat[col][2*i-k])
				k++;
			k--;
			z[col][i]=k-i;
			if(k>R)
			{
				R=k;
				C=i;
			}
		}
		else z[col][i]=z[col][aux];
	}
}
int main()
{
	int n,m;
	in>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			in>>mat[i][j];
		mat[i][0]=-1;
		manacher(i,m);
	}
	int ans=0;
	for(int i=2;i<m;i++)
	{
		int top=1;
		st[0]=0;;
		st[1]=0;
		z[n+1][i]=-1;
		z[0][i]=-1;
		for(int j=1;j<=n+1;j++)
		{
			while(top && z[j][i]<=z[st[top]][i])
			{
				ans=max(ans,(z[st[top]][i]*2+1)*(j-st[top-1]-1));
				top--;
			}
			top++;
			st[top]=j;
		}
	}
	out<<ans;
	return 0;
}