Cod sursa(job #636715)

Utilizator PetcuIoanPetcu Ioan Vlad PetcuIoan Data 19 noiembrie 2011 22:44:31
Problema DreptPal Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 2.34 kb
#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;

int n,m,sol,st1[1002],st2[1002],li[1002],ri[1002],p[1011][2020],a[1001][1001];

void read()
{
    assert(freopen("dreptpal.in","r",stdin)!=NULL);
    scanf("%d%d",&n,&m);
    int i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;++i)
        a[i][0]=2000000000;
}

void do_smen()
{
    int i,j,l,k,t;
    l=2*m-1;
    for(i=1;i<=n;++i)
    {
        t=0;
        k=0;
        for(j=1;j<=l;++j)
        {
            if(t<k)
            {
                p[i][j]=p[i][j-2*t];
                ++t;
            }
            else
            {
                if(j%2==0)
                {
                    for(k=1;a[i][(j+1)/2+k]==a[i][(j+1)/2-k];++k);
                    k--;
                    p[i][j]=k*2;
                    k=k*2;
                    t=1;
                }
                else
                {
                    for(k=0;a[i][(j+1)/2+k]==a[i][(j+1)/2-k];++k);
                    k--;
                    p[i][j]=k*2+1;
                    k=k*2;
                    t=1;
                }
            }
            printf("%d ",p[i][j]);
        }
        printf("\n");
    }
}

void solve()
{
    do_smen();
    int i,j;
    for(i=1;i<=m;++i)
    {
        for(j=1;j<=n;++j)
        {
            while(st1[0] && p[st1[st1[0]]][2*i-1]>p[j][2*i-1])
                {
                    st1[st1[0]]=0;
                    --st1[0];
                }
            li[j]=j-st1[st1[0]]-1;
            st1[++st1[0]]=j;
        }
        for(j=n;j>0;--j)
        {
            while(st2[0] && p[st2[st2[0]]][2*i-1]>p[j][2*i-1])
            {
                st2[st2[0]]=0;
                --st2[0];
            }
            if(st2[0]==0)
                ri[j]=n-j;
            else
                ri[j]=st2[st2[0]]-j;
            st2[++st2[0]]=j;
        }
        for(j=1;j<=n;++j)
            sol=max(sol,p[j][2*i-1]*(ri[j]+li[j]));
        while(st2[0])
        {
            st2[st2[0]]=0;
            --st2[0];
        }
        while(st1[0])
        {
            st1[st1[0]]=0;
            --st1[0];
        }
    }
}

void write()
{
    //assert(freopen("dreptpal.out","w",stdout)!=NULL);
    printf("%d",sol);
}

int main()
{
    assert(freopen("dreptpal.out","w",stdout)!=NULL);
    read();
    solve();
    write();
    return 0;
}