Cod sursa(job #1345699)

Utilizator Athena99Anghel Anca Athena99 Data 17 februarie 2015 20:14:12
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <stack>

using namespace std;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

const int nmax= 1000;

int n, m;
int v[nmax+2], d[nmax+1][nmax+1], x[nmax+1], y[nmax+1];

stack <int> s;

int main(  ) {
    fin>>n>>m;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>v[j];
        }
        v[m+1]= -1;

        for ( int j= 1, right= 0, pos= 0; j<=m; ++j ) {
            if ( j>right ) {
                d[i][j]= 1;

                int k;
                for ( k= 1; v[j-k]==v[j+k]; ++k ) ; --k;
                d[i][j]+= k, pos= j, right= j+k;
            } else {
                if ( j+d[i][2*pos-j]-1<right ) {
                    d[i][j]= d[i][2*pos-j];
                } else {
                    d[i][j]= right-j+1;

                    int k;
                    for ( k= 1; v[2*j-right-k]==v[right+k]; ++k ) ; --k;
                    d[i][j]+= k, pos= j, right+= k;
                }
            }
        }
    }

    int sol= n;
    for ( int j= 1; j<=m; ++j ) {
        for ( int i= 1; i<=n; ++i ) {
            v[i]= d[i][j];
        }

        for ( ; !s.empty(); s.pop() ) ;
        for ( int i= 1; i<=n; ++i ) {
            for ( ; !s.empty() && v[i]<=v[s.top()]; s.pop() ) ;
            if ( s.empty() ) x[i]= 1;
            else x[i]= s.top()+1;

            s.push(i);
        }
        for ( ; !s.empty(); s.pop() ) ;
        for ( int i= n; i>=1; --i ) {
            for ( ; !s.empty() && v[i]<=v[s.top()]; s.pop() ) ;
            if ( s.empty() ) y[i]= n;
            else y[i]= s.top()-1;

            s.push(i);
        }

        for ( int i= 1; i<=n; ++i ) {
            sol= max(sol, (y[i]-x[i]+1)*(2*v[i]-1));
        }
    }

    fout<<sol<<"\n";

    return 0;
}