Cod sursa(job #1943340)

Utilizator borcanirobertBorcani Robert borcanirobert Data 28 martie 2017 15:18:51
Problema DreptPal Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

const int MAX = 1000;
int N, M;
int A[MAX][MAX];
int p[MAX][MAX];

void Read();
void Solve();
void Manacher( int l );
int Expand( int l, int i, int j );
int AreaInHist( vector<int>& s );

int main()
{
    Read();
    Solve();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> N >> M;
    for ( int i = 0; i < N; ++i )
        for ( int j = 0; j < M; ++j )
            fin >> A[i][j];
}

void Solve()
{
    int i, j;
    for ( i = 0; i < N; ++i )
    {
        Manacher(i);

     /*   for ( j = 0; j < M; ++j )
            fout << p[i][j] << ' ';
        fout << '\n';   */
    }

    vector<int> s(N);
    int maxArea{0};
    for ( j = 0; j < M; ++j )
    {
        for ( i = 0; i < N; ++i )
            s[i] = p[i][j];

        maxArea = max( maxArea, AreaInHist(s) );
    }

    fout << maxArea << '\n';
}

void Manacher( int l )
{
    p[l][0] = 1;
    int L{0}, C{0}, R{0}, ip;

    for ( int i = 1; i < M; ++i )
    {
        if ( R >= i )
        {
            ip = C - ( i - C );
            p[l][i] = min(p[l][ip], (ip - L) * 2 + 1);
            if ( ip == L )
                p[l][i] += Expand(l, i - ( R + 1 - i ), R + 1);
        }
        else
            p[l][i] = Expand(l, i - 1, i + 1) + 1;

        if ( i + (p[l][i] / 2) > R )
            L = i - (p[l][i] / 2), R = i + (p[l][i] / 2), C = i;
    }
}

int Expand( int l, int i, int j )
{
    int cnt{0};
    while ( ( i >= 0 && j < M ) && A[l][i] == A[l][j] )
        --i, ++j, cnt += 2;
    return cnt;
}

int AreaInHist( vector<int>& s )
{
    stack<int> st;
    int tp, i{0};
    int area, maxArea{0};

    while ( i < N )
    {
        if ( st.empty() || s[st.top()] <= s[i] )
            st.push(i++);
        else
        {
            tp = st.top(); st.pop();
            area = s[tp] * ( st.empty() ? i : ( i - st.top() - 1 ) );

            maxArea = max( area, maxArea );
        }
    }

    while ( !st.empty() )
    {
        tp = st.top(); st.pop();
        area = s[tp] * ( st.empty() ? i : ( i - st.top() - 1 ) );

        maxArea = max( area, maxArea );
    }

    return maxArea;
}