Cod sursa(job #1171672)

Utilizator ThomasFMI Suditu Thomas Thomas Data 16 aprilie 2014 01:35:59
Problema DreptPal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMax 1005

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

int n,m;
int M[NMax][NMax];
int P[NMax][NMax];
pair< int,int > v[NMax];
pair< int,int > per[NMax];
int val[NMax];
int valf[NMax];

#define crt v[i].second

int solve(int j)
{
    int i;
    for(i=1;i<=n;i++)
    {
        v[i].first=P[i][j];
        v[i].second=i;
        val[i]=0;
    }
    sort(v+1,v+n+1);
    for(i=n;i>=1;i--)
    {
        if(!val[crt-1] && !val[crt+1]) per[crt].first=per[crt].second=crt, val[crt]=valf[crt]=1;
        else if(val[crt-1] && val[crt+1])
        {
            per[per[crt-1].first].second=per[crt+1].second;
            per[per[crt+1].second].first=per[crt-1].first;
            valf[crt]=val[crt]=val[crt-1]+val[crt+1];
            val[per[crt-1].first]=val[crt];
            val[per[crt+1].second]=val[crt];
        }
        else if(val[crt-1])
        {
            per[per[crt-1].first].second=crt;
            per[crt].first=per[crt-1].first;
            valf[crt]=val[crt]=1+val[crt-1];
            val[per[crt-1].first]=val[crt];
        }
        else
        {
            per[per[crt+1].second].first=crt;
            per[crt].second=per[crt+1].second;
            valf[crt]=val[crt]=1+val[crt+1];
            val[per[crt+1].second]=val[crt];
        }
    }

    int mx=0;
    for(i=1;i<=n;i++)
    {
        valf[i]*=P[i][j];
        if(mx<valf[i]) mx=valf[i];
    }

    return mx;
}

int main()
{
    int i,j;
    int L,R,C,p,d;

    f>>n>>m;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++) f>>M[i][j];

        M[i][0]=-1;
        C=L=R=0;

        for(j=1;j<=m;j++)
        {
            if(j>R)
            {
                p=1;
                while(M[i][j-p]==M[i][j+p]) p++;
                p--;
                P[i][j]=(p<<1)|1;
                L=j-p,R=j+p,C=j;
            }
            else
            {
                d=j-C;

                if(C-d-P[i][C-d]/2<L) p=C-d-L+1;
                else p=P[i][C-d]/2+1;

                while(M[i][j-p]==M[i][j+p]) p++;
                p--;
                P[i][j]=(p<<1)|1;
                if(j+P[i][j]/2>R) L=j-p,R=j+p,C=j;
            }
        }
    }

    int mx=0,nr;
    for(i=1;i<=m;i++)
    {
        nr=solve(i);
        if(nr>mx) mx=nr;
    }

    g<<mx<<"\n";

    f.close();
    g.close();
    return 0;
}