Pagini recente » Cod sursa (job #2140784) | Cod sursa (job #1176535) | Cod sursa (job #92933) | Cod sursa (job #1874663) | Cod sursa (job #1943340)
#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;
}