Cod sursa(job #2595880)

Utilizator armigheGheorghe Liviu Armand armighe Data 8 aprilie 2020 16:24:18
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include<fstream>
#include<stack>
#include<algorithm>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m,a[1002][1002],manacher[1002][1002];
stack<int>s;
void Manacher(int x)
{
    int i,st,dr,poz=0,l=0,ll;
    for(i=1;i<=m;i++)
    {
        if(i>poz+l)
        {
            poz=i;
            l=0;
            st=i-1;
            dr=i+1;
            while(st>=1&&dr<=m&&a[x][st]==a[x][dr])
            {
                st--;
                dr++;
                l++;
            }
            manacher[x][i]=l;
        }
        else
        {
            if(i+manacher[x][2*poz-i]<poz+l)
                manacher[x][i]=manacher[x][2*poz-i];
            else
            if(i+manacher[x][2*poz-i]>poz+l)
                manacher[x][i]=poz+l-i;
            else
            {
                st=i-manacher[x][2*poz-i]-1;
                dr=poz+l+1;
                ll=0;
                while(st>=1&&dr<=m&&a[x][st]==a[x][dr])
                {
                    st--;
                    dr++;
                    ll++;
                }
                manacher[x][i]=poz+l-i;
                if(ll!=0)
                {
                    manacher[x][i]+=ll;
                    poz=i;
                    l=manacher[x][i];
                }
            }
        }
    }
}

int main()
{
    int i,j,sol=0,x,y;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            f>>a[i][j];
        Manacher(i);
    }
    for(j=1;j<=m;j++)
    {
        for(i=1;i<=n;i++)
        {
            while(!s.empty()&&manacher[s.top()][j]>manacher[i][j])
            {
                x=manacher[s.top()][j];
                s.pop();
                if(s.empty())
                    y=0;
                else
                    y=s.top();
                sol=max(sol,(2*x+1)*(i-y-1));
            }
            s.push(i);
        }
        while(!s.empty())
        {
            x=manacher[s.top()][j];
            s.pop();
            if(s.empty())
                y=0;
            else
                y=s.top();
            sol=max(sol,(2*x+1)*(n-y));
        }
    }
    g<<sol;
    return 0;
}