Cod sursa(job #2649225)

Utilizator etienAndrone Stefan etien Data 13 septembrie 2020 16:53:31
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int mat[1002][1002];
int d1[1002][1002];
int st[1002],dr[1002];
stack<int>s;
int main()
{
    int n,m,i,j;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>mat[i][j];
        }
    for(i=1;i<=n;i++)
    {
        d1[i][1]=1;
        int l=1,r=1;
        for(j=2;j<=m;j++)
        {
            if(j>r)
            {
                r=j;
                l=j;
                while(l>=1&&r<=m&&mat[i][r]==mat[i][l])
                {
                    r++;
                    l--;
                    d1[i][j]++;
                }
                r--;
                l++;
            }
            else
            {
                d1[i][j]=min(d1[i][r+l-j],r-j+1);
                if(r<j+d1[i][r+l-j])
                {
                    r=j+d1[i][j];
                    l=j-d1[i][j];
                    while(l>=1&&r<=m&&mat[i][r]==mat[i][l])
                    {
                        r++;
                        l--;
                        d1[i][j]++;
                    }
                    r--;
                    l++;
                }
            }
        }
    }
    int maxi=0;
    for(j=1;j<=m;j++)
    {
        s.push(0);
        for(i=1;i<=n;i++)
        {
            while(!s.empty()&&d1[s.top()][j]>=d1[i][j])
            {
                s.pop();
            }
            st[i]=s.top();
            s.push(i);
        }
        while(!s.empty())
            s.pop();
        s.push(n+1);
        for(i=n;i>=1;i--)
        {
            while(!s.empty()&&d1[s.top()][j]>=d1[i][j])
            {
                s.pop();
            }
            dr[i]=s.top();
            s.push(i);
        }
        for(i=1;i<=n;i++)
            if(maxi<(2*d1[i][j]-1)*(dr[i]-st[i]-1))
                maxi=(2*d1[i][j]-1)*(dr[i]-st[i]-1);
        while(!s.empty())
            s.pop();
    }
    fout<<maxi;
    return 0;
}