Cod sursa(job #1346643)

Utilizator ade_tomiEnache Adelina ade_tomi Data 18 februarie 2015 14:57:12
Problema DreptPal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<stdio.h>
#include<iostream>
using namespace std;
int p[1005][1005],a[1005][1005],i,j,n,m,k,sus[1005],jos[1005],st[1005],nr,sol;
class InputReader {
    public:
        InputReader() {}
        InputReader(const char *file_name) {
            input_file = fopen(file_name, "r");
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
        inline InputReader &operator >>(int &n) {
            while(buffer[cursor] < '0' || buffer[cursor] > '9') {
                advance();
            }
            n = 0;
            while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
                n = n * 10 + buffer[cursor] - '0';
                advance();
            }
            return *this;
        }
    private:
        FILE *input_file;
        static const int SIZE = 1 << 17;
        int cursor;
        char buffer[SIZE];
        inline void advance() {
            ++ cursor;
            if(cursor == SIZE) {
                cursor = 0;
                fread(buffer, SIZE, 1, input_file);
            }
        }
};
void extinde (int q)
{
    while(q+p[i][q]+1<=m&&q-p[i][q]-1>0&&a[i][q+p[i][q]+1]==a[i][q-p[i][q]-1])
        p[i][q]++;
}
int max(int a, int b)
{

    if(a>b)
        return a;
    return b;
}
int main()
{

    freopen("dreptpal.in","r",stdin);
    freopen("dreptpal.out","w",stdout);
   cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            cin>>a[i][j];
    for(i=1;i<=n;i++)
    {

        p[i][1]=0;
        k=1;
        for(j=2;j<=m;j++)
        {

            if(p[i][k]+k<j)
                extinde(j);
            else
            {

                if(p[i][k]+k<=j+p[i][2*k-j])
                {

                    p[i][j]=p[i][2*k-j];
                    extinde(j);
                }
                else
                    p[i][j]=p[i][2*k-j];
            }
        }
    }

    for(j=1;j<=m;j++)
    {

        nr=0;
        st[0]=0;
        for(i=1;i<=n;i++)
        {

            while(nr>0&&p[st[nr]][j]>=p[i][j])
                nr--;
            sus[i]=st[nr];
            nr++;
            st[nr]=i;

        }
        nr=0;
        st[0]=n+1;
        for(i=n;i>=1;i--)
        {

            while(nr>0&&p[st[nr]][j]>=p[i][j])
                nr--;
            jos[i]=st[nr];
            nr++;
            st[nr]=i;

        }
        for(i=1;i<=n;i++)
            sol=max(sol,(jos[i]-sus[i]-1)*(p[i][j]*2+1));
    }
    printf("%d",sol);

    return 0;
}