Pagini recente » Cod sursa (job #832746) | Cod sursa (job #2073808) | Cod sursa (job #776714) | Profil angel_raluk | Cod sursa (job #2008938)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
void Manacher(int v[], int sz, int ret[])
{
int R = -1, C = 0, rad;
for(int i = 1; i <= sz; ++i)
{
if(i <= R)
rad = min(ret[2 * C - i], R - i) + 1;
else
rad = 0;
while(i - rad >= 1 && i + rad <= sz && v[i-rad] == v[i+rad])
rad++;
ret[i] = rad - 1;
if(i + ret[i] - 1 > R)
{
C = i;
R = i + ret[i] - 1;
}
}
}
const int nMax = 1005;
const int mMax = 1005;
int n, m;
int a[nMax][mMax];
int pal[nMax][mMax];
int rasp;
void citire()
{
ifstream in("dreptpal.in");
in >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
in >> a[i][j];
in.close();
}
int smallerSt[nMax], smallerDr[nMax];
void rezolvare()
{
for(int i = 1; i <= n; ++i)
Manacher(a[i], m, pal[i]);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
pal[i][j] = 2 * pal[i][j] + 1;
for(int col = 1; col <= m; col++)
{
stack<pair<int, int> > st;
st.push(make_pair(0, 0));
for(int i = 1; i <= n; ++i)
{
while(pal[i][col] <= st.top().first)
st.pop();
smallerSt[i] = st.top().second;
st.push(make_pair(pal[i][col], i));
}
while(st.empty() == false)
st.pop();
st.push(make_pair(0, n + 1));
for(int i = n; i >= 1; --i)
{
while(pal[i][col] <= st.top().first)
st.pop();
smallerDr[i] = st.top().second;
st.push(make_pair(pal[i][col], i));
}
for(int i = 1; i <= n; ++i)
rasp = max(rasp, pal[i][col] * (smallerDr[i] - smallerSt[i] - 1));
}
}
void afisare()
{
ofstream out("dreptpal.out");
out << rasp;
out.close();
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}