Pagini recente » Cod sursa (job #1995874) | Arhiva de probleme | Cod sursa (job #1243668) | Istoria paginii utilizator/butler1234 | Cod sursa (job #2021918)
#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;
}