Pagini recente » Cod sursa (job #416864) | Cod sursa (job #2056573) | Cod sursa (job #771298) | Cod sursa (job #1933714) | Cod sursa (job #2008697)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
void Manacher(int v[], int sz, int ret[])
{
ret[1] = 0;
int st, dr;
for(int i = 2; i < sz; ++i)
{
if(v[i-1] == v[i+1])
{
st = i - ret[i-1];
dr = i + ret[i-1];
ret[i] = ret[i-1] - 1;
while(st >= 1 && dr <= sz && v[st--] == v[dr++])
ret[i]++;
}
else
ret[i] = 0;
}
ret[sz] = 0;
}
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;
}