Cod sursa(job #2021918)

Utilizator HumikoPostu Alexandru Humiko Data 14 septembrie 2017 22:24:18
Problema DreptPal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <stack>
#include <vector>

using namespace std;

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

int manacher[1002][1002], mat[1002][1002];
stack <int> stiva;
vector <int> v;

void Manacher (int n, int m)
{
    for ( int i = 1; i <= n; ++i )
    {
        int mij = 0;
        for ( int j = 1; j <= m; ++j )
        {
            if ( j > mij + manacher[i][mij] )
            {
                while ( mat[i][j+manacher[i][j]+1] == mat[i][j-manacher[i][j]-1] && j - manacher[i][j] > 1 && j + manacher[i][j] < m  )
                    manacher[i][j]++;
                mij = j;
            }
            else
            {
                manacher[i][j] = min ( mij + manacher[i][mij] - j, manacher[i][mij-(j-mij)] );
                while ( mat[i][j+manacher[i][j]+1] == mat[i][j-manacher[i][j]-1] && j - manacher[i][j] > 1 && j + manacher[i][j] < m )
                    manacher[i][j]++;
                if ( mij + manacher[i][mij] <= j + manacher[i][j])
                    mij = j;
            }
        }
    }
}

int arie ()
{
    int raspuns = -1, last;
    while ( !stiva.empty() )
        stiva.pop();
    stiva.push(0);
    for ( int i = 0; i <= v.size(); ++i )
    {
        while ( v[i] < v[stiva.top()] && stiva.size() > 1 )
        {
            last = v[stiva.top()];
            stiva.pop();
            raspuns = max (raspuns, last * (i - stiva.top() - 1) );
        }
        stiva.push(i);
    }
    return raspuns;
}

int main()
{
    int n, m, strb = 0, maxim = -1;
    fin>>n>>m;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            fin>>mat[i][j];
    Manacher (n, m);
    for ( int i = 1; i <= n; ++i )
    {
        v.clear();
        v.push_back(0);
        for ( int j = 1; j <= m; ++j)
        {
            v.push_back(2*manacher[i][j]+1);
        }
        v.push_back(0);
        ;
        maxim = max (maxim, arie());
    }
    fout<<maxim;
}