Cod sursa(job #2457960)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 19 septembrie 2019 10:38:41
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 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);
    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 ( i + ( p[l][ip] / 2 ) >= R )
	
                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;
	
}