Cod sursa(job #1867240)

Utilizator razvan99hHorhat Razvan razvan99h Data 3 februarie 2017 21:21:33
Problema DreptPal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#define DM 1002
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int n, m, i, j, t[DM][DM*2], jj, r, c, st[DM], stpoz[DM], top, val, nr, aria;
short  lps[DM][DM*2];
bool ok, expand;

void Manacher()//caz general
{
    m=2*m+1;
    //aplicam algoritmul lui Manacher pe fiecare linie
    for(i=1;i<=n;i++)
    {
        lps[i][1]=c=1;
        r=2;
        for(j=2;j<=m;j++)
        {
            expand=0;
            jj=2*c-j;
            if(j>=r)
                expand=1;
            else
            {
                if(lps[i][jj]<=r-j)
                    lps[i][j]=lps[i][jj];
                if(lps[i][jj]==r-j)
                    expand=1;
                if(lps[i][jj]>r-j)
                {
                    lps[i][j]=r-j;
                    expand=1;
                }
            }
            if(expand)
            {
                ok=1;
                while(j-lps[i][j]>0 && j+lps[i][j]<m && ok)
                {
                    if((j-lps[i][j]-1)%2==0)
                        lps[i][j]++;
                    else
                    {
                        if(t[i][j-lps[i][j]-1] == t[i][j+lps[i][j]+1])
                            lps[i][j]++;
                        else ok=0;
                    }
                }
            }
            if(lps[i][j]>r)
            {
                c=j;
                r=j+lps[i][j];
            }
        }
    }
}
int main()
{
    fin>>n>>m;

    for(i=1;i<=n;i++)
    {
        t[i][0]=-1;
        for(j=1;j<=m;j++)
        {
            fin>>t[i][2*j-1];
            t[i][2*j]=-1;
        }
    }
    Manacher();

    for(j=1;j<m;j++)
        if(j%2!=0)
        {
            for(i=1;i<=n;i++)
            {
                val=lps[i][j];
                if(top==0 || val>st[top])
                {
                    top++;
                    st[top]=val;
                    stpoz[top]=i;
                }
                else
                {
                    int last=i;
                    while(top>0 && val<=st[top])
                    {
                        last=stpoz[top];
                        aria=max(aria,(i-stpoz[top])*st[top]);
                        top--;
                    }
                    top++;
                    st[top]=val;
                    stpoz[top]=last;
                }
            }
            while(top>0)
            {
                aria=max(aria,(n-stpoz[top])*st[top]);
                top--;
            }
        }
    fout<<aria;

    return 0;
}