Cod sursa(job #2315721)

Utilizator iulianrotaruRotaru Gheorghe-Iulian iulianrotaru Data 10 ianuarie 2019 14:37:11
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m,S[1<<10],st[1<<10],dr[1<<10],a[1<<10],p[1<<10][1<<10];
void Manacher(int i)
{
	a[0]=-1;
	a[m+1]=-2;
	int r=0,c=0;
	for(int j=1;j<=m;++j)
        f>>a[j];
	for(int j=1;j<=m;++j)
	{
		int cur=0;
		if(j<r)
            cur=min(r-j,p[i][2*c-j]);
		while(a[j+cur+1]==a[j-cur-1]) cur++;
		if(j+cur>r)
		{
			r=j+cur;
			c=j;
		}
		p[i][j]=cur;
	}
}
int main()
{
	f>>n>>m;
	for(int i=1;i<=n;++i)
        Manacher(i);
	int sol=0;
	for(int j=1;j<=m;++j)
	{
		int k=0;
		S[k]=0;
		for(int i=1;i<=n;++i)
		{
			while(k&&p[i][j]<=p[S[k]][j]) k--;
			st[i]=S[k]+1;
			S[++k]=i;
		}
		k=0;
		S[k]=n+1;
		for(int i=n;i>0;--i)
		{
			while(k&&p[i][j]<=p[S[k]][j]) k--;
			dr[i]=S[k]-1;
			S[++k]=i;
		}
		for(int i=1;i<=n;++i)
			sol=max(sol,(dr[i]-st[i]+1)*(p[i][j]*2+1));
	}
	g<<sol;
	return 0;
}