Cod sursa(job #2486135)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 2 noiembrie 2019 12:50:57
Problema DreptPal Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f ("dreptpal.in");
ofstream g ("dreptpal.out");

int mak[1000][1000], vek[1000][1000];
int st[1000], dr[1000];

int n,m;
int stv[1000];
int stvv[1000];

int main()
{
    f >> n >> m;
    for(int i=1; i<=n; i++)
       for(int j=1; j<=m; j++)
          f>>mak[i][j];
    for(int i=1;i<=n;++i)
    {
        int l=0, r=0;
        int ras;
        for(int j=1;j<=m;++j)
        {
            long long ras=2*l-j;
            if(j<=r)
                vek[i][j]=min(r-j, vek[i][ras]);
            while(mak[i][j+vek[i][j]] == mak[i][j-vek[i][j]] && j+vek[i][j]<=m)
                vek[i][j]++;

            if(vek[i][j]+j>r)
            {
                l=j;
                r=vek[i][j]+j;
            }
        }
    }
    for(int j=1; j<=n; j++)
    {
        for(int i=1; i<=m; i++)
        {
            vek[j][i]*=2;
            vek[j][i]--;
          //  cout<<vek[j][i]<<" ";

        }
     //   cout<<"\n";

    }
    int therealslimshady=0;

    int maxxx=0;
    for(int c=1;c<=m;++c)
    {
        maxxx=0;

        int k=1;
       // int nr=0;
        for(int i=0;i<=1+n;++i)
        {

            while(k>1 && vek[stv[k]][c]>=vek[i][c])
            {
                k--;
            }

            st[i]=stv[k];
            k++;
            stv[k]=i;



        }
        int kk=1;
        //int nrk=0;

        for(int i=1+n;i>=0;--i)
        {

              while(kk>1 && vek[stvv[kk]][c]>=vek[i][c])
            {
                kk--;
            }
            dr[i]=stvv[kk];
            kk++;
            stvv[kk]=i;



        }


     //   cout<<"col: "<<c<<"\n";
        for(int i=1;i<=n;++i)
        {

            //cout<<i<<"  st:"<<st[i]<<"  dr:"<<dr[i]<<"\n";
            if(maxxx < (dr[i]-st[i]-1)*vek[i][c])
                maxxx  = (dr[i]-st[i]-1)*vek[i][c];
        }
        if(therealslimshady<maxxx)
            therealslimshady=maxxx;

    }
    g<<therealslimshady;
    return 0;
}