Cod sursa(job #1003519)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 30 septembrie 2013 21:00:44
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <stack>

using namespace std;

int mat[1005][1005],man[1005][1005];
int sus[1005][1005];
int jos[1005][1005];

stack<int> stiva;


int main()
{
    ifstream cin("dreptpal.in");
    ofstream cout("dreptpal.out");

    int centru,dif,maximul=-1;
    int n=0,m=0,i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            cin>>mat[i][j];
    for(i=1;i<=n;i++)
    {
        centru=0;
        for(j=1;j<=m;j++)
        {
            if((centru+man[i][centru])<j)
                dif=1;
            else if((2*centru-j-man[i][2*centru-j])>(centru-man[i][centru]))
            {
                man[i][j]=man[i][2*centru-j];
                continue;
            }
            else
                dif=2*centru-j-(centru-man[i][centru])+1;
            for(;((j-dif)>=1) && ((j+dif)<=m) && dif<m;dif++)
                if(mat[i][j-dif]!=mat[i][j+dif])
                    break;
            man[i][j]=dif-1;
            if((centru+man[i][centru])<(j+man[i][j]))
                centru=j;
        }
    }

    int varf;
    for(i=1;i<=m;i++)
    {
        //init stv
        for(j=1;j<=n;j++)
        {
            while(!stiva.empty())
                if(man[stiva.top()][i]>=man[j][i])
                    stiva.pop();
                else
                    break;

            if(stiva.empty())
                varf=0;
            else
                varf=stiva.top();
            stiva.push(j);
            sus[j][i]=(j-varf)*(man[j][i]*2+1);
        }
        while(!stiva.empty())
            stiva.pop();

        //init stv
        for(j=n;j>=1;j--)
        {
            while(!stiva.empty())
                if(man[stiva.top()][i]>=man[j][i])
                    stiva.pop();
                else
                    break;

            if(stiva.empty())
                varf=n+1;
            else
                varf=stiva.top();
            stiva.push(j);
            jos[j][i]=(varf-j-1)*(man[j][i]*2+1)+sus[j][i];
            if(jos[j][i]>maximul)
                maximul=jos[j][i];

        }
        while(!stiva.empty())
            stiva.pop();
    }
    cout<<maximul<<'\n';

    cin.close();
    cout.close();
    return 0;
}