Cod sursa(job #2507019)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 9 decembrie 2019 13:43:14
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
int l[1002][1002],s[1002],h[1002],st[1002];
void man(int a[],int n)
{
    int i,j,c=1,p=1;
	for(i=2;i<=n;i++)
	{
		j=min(a[c*2-i],max(p-i,0));
		for(;i+j<n&&j<i&&s[i+j+1]==s[i-j-1];j++);
		if(i+j>p)
			c=i,p=i+j;
		a[i]=j;
	}
}
int main()
{
    int n,m,i,j,k,mx=0;
    in>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            in>>s[j];
        man(l[i],m);
    }
    for(j=1;j<=m;j++)
    {
        for(i=1,k=st[0]=0;i<=n;i++)
        {
            for(;k&&l[i][j]<=l[st[k]][j];k--);
            h[i]=st[k];
            st[++k]=i;
        }
        st[0]=n+1;
        for(i=n,k=0;i;i--)
        {
            for(;k&&l[i][j]<=l[st[k]][j];k--);
            mx=max(mx,(st[k]-h[i]-1)*(l[i][j]*2+1));
            st[++k]=i;
        }
    }
    out<<mx;
    return 0;
}