# Cod sursa(job #2457960)

Utilizator Data 19 septembrie 2019 10:38:41 DreptPal 100 cpp-64 done Arhiva de probleme 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;

}
``````