Cod sursa(job #1303736)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 28 decembrie 2014 13:11:52
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;

#define NMAX 1002

int a[NMAX][NMAX],st[NMAX],v[NMAX],c[NMAX],l[NMAX],r[NMAX];

void manacher(int s[], int p[], int n)
{
    int R,C,i,j;
    R=1;
    C=1;
    s[0]=-1;
	s[n+1]=-2;
    for(i=2;i<=n-1;i++) {
        j=2*C-i;
        if(i+p[j]<R)
            p[i]=p[j];
        else {
            if(R>i)
                p[i]=R-i;
            else p[i]=0;
            while(s[i+p[i]+1]==s[i-p[i]-1])
                p[i]++;
        }
        if(i+p[i]>R) {
            R=p[i]+i;
            C=i;
        }
    }
}

int main ()
{
	int n,m,i,j,p,sol;
	ifstream f("dreptpal.in");
	ofstream g("dreptpal.out");
	f>>n>>m;
	for(i=1;i<=n;i++) {
		for(j=1;j<=m;j++)
			f>>c[j];
		manacher(c,a[i],m);
	}
	f.close();
	sol=-1;
	for(j=1;j<=m;j++) {
		for(i=1;i<=n;i++)
			v[i]=a[i][j];
		p=0;
		st[0]=0;
		for(i=1;i<=n;i++) {
			while(p && v[st[p]]>=v[i])
				p--;
			l[i]=st[p]+1;
			st[++p]=i;
		}
		p=0;
		st[0]=n+1;
		for(i=n;i>=1;i--) {
			while(p && v[st[p]]>=v[i])
				p--;
			r[i]=st[p]-1;
			st[++p]=i;
		}
		for(i=1;i<=n;i++)
			sol=max(sol,(2*v[i]+1)*(r[i]-l[i]+1));
	}
	g<<sol;
	g.close();
	return 0;
}