Cod sursa(job #2953934)

Utilizator Zed1YasuoAlex Birsan Zed1Yasuo Data 12 decembrie 2022 17:57:57
Problema Cerere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n,m,mx,x,s[1003],b[1003][1003],st1[1003],dr1[1003],a[1003][1003];
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            f>>a[i][j];
    for(int i=1; i<=n; i++)
        a[i][0]=-99999,a[i][m+1]=-999;
    for(int i=1; i<=n; i++)
    {
        int st=1,dr=1;
        for(int j=1; j<=m; j++)
        {
            b[i][j]=max(1,min(b[i][st+dr-j],dr-j));
            while(a[i][j-b[i][j]]==a[i][j+b[i][j]])
                b[i][j]++;
            if(dr<j+b[i][j])
                st=j-b[i][j],dr=j+b[i][j];
        }
    }
    for(int j=1; j<=m; j++)
    {
        for(int t=1; t<=n; t++)
            st1[t]=dr1[t]=0;
            int nr=0;
        for(int t=1; t<=n; t++)
            if(t==1)
                nr=1,s[1]=1;
            else
            {
                while(nr&&b[t][j]<b[s[nr]][j])
                {
                    dr1[s[nr]]=t;
                    nr--;
                }
                s[++nr]=t;
            }
        for(int i=1; i<=nr; i++)
            dr1[s[i]]=n+1;
        for(int t=n; t>0; t--)
            if(t==n)
                nr=1,s[1]=n;
            else
            {
                while(nr&&b[t][j]<b[s[nr]][j])
                {
                    st1[s[nr]]=t;
                    nr--;
                }
                s[++nr]=t;
            }
        for(int i=1; i<=nr; i++)
            st1[s[i]]=0;
        for(int i=1; i<=n; i++)
            mx=max(mx,(dr1[i]-st1[i]-1)*(b[i][j]*2-1));
    }
    g<<mx;
    return 0;
}