Pagini recente » Rating Denisa Lepadatu (blackbear26) | Cod sursa (job #2783879) | Cod sursa (job #3263340) | Cod sursa (job #884022) | Cod sursa (job #2693454)
#include <fstream>
using namespace std;
const int NMAX = 1000;
const int MMAX = 1000;
int n, m;
int x[1 + NMAX][1 + MMAX];
int lung[1 + NMAX + 1][1 + MMAX];
int stSize;
int st[1 + NMAX + 1];
int sus[1 + NMAX];
int jos[1 + NMAX];
void extindere(int linie, int index)
{
while (1 <= index - lung[linie][index] && index + lung[linie][index] <= m && x[linie][index - lung[linie][index]] == x[linie][index + lung[linie][index]])
{
lung[linie][index]++;
}
lung[linie][index]--;
}
int main()
{
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
in >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
in >> x[i][j];
}
}
// Manacher
for (int i = 1; i <= n; i++)
{
int pozPal = 0;
for (int j = 1; j <= m; j++)
{
if (pozPal + lung[i][pozPal] >= j)
{
int sim = pozPal - (j - pozPal);
if (sim - lung[i][sim] > pozPal - lung[i][pozPal])
{
lung[i][j] = lung[i][sim];
}
else
{
lung[i][j] = pozPal + lung[i][pozPal] - j;
extindere(i, j);
}
}
else
{
extindere(i, j);
}
if (j + lung[i][j] > pozPal + lung[i][pozPal])
{
pozPal = j;
}
}
}
int sol = 0;
for (int j = 1; j <= m; j++)
{
// Limita sus
stSize = 1;
st[1] = 0;
for (int i = 1; i <= n; i++)
{
while (stSize >= 0 && lung[st[stSize]][j] >= lung[i][j])
stSize--;
sus[i] = st[stSize] + 1;
stSize++;
st[stSize] = i;
}
// Limita jos
stSize = 1;
st[1] = n + 1;
for (int i = n; i >= 1; i--)
{
while (stSize >= 0 && lung[st[stSize]][j] >= lung[i][j])
stSize--;
jos[i] = st[stSize] - 1;
stSize++;
st[stSize] = i;
}
// Sol
for (int i = 1; i <= n; ++i)
{
sol = max(sol, (jos[i] - sus[i] + 1) * (2 * lung[i][j] + 1));
}
}
out << sol << '\n';
return 0;
}