Pagini recente » Cod sursa (job #1940529) | Cod sursa (job #2880932) | Cod sursa (job #36) | Cod sursa (job #2445585) | Cod sursa (job #3197966)
#include <fstream>
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n, m, a[1005], st[1005], dr[1005], s[1005], p[1005][1005];
void Manacher(int i)
{
a[0] = -1;
a[m + 1] = -2;
int r, c;
for (int j = 1; j <= m; ++j) {
f >> a[j];
}
for (int j = 1; j <= m; ++j) {
int cur = 0;
if (j < r) {
cur = min(r - j, p[i][2 * c - j]);
}
while (a[j + cur + 1] == a[j - cur - 1]) {
cur++;
}
if (j + cur > r) {
r = j + cur;
c = j;
}
p[i][j] = cur;
}
}
int main()
{
f >> n >> m;
for(int i = 1; i <= n; ++i) {
Manacher(i);
}
int sol = 0;
for (int j = 1; j <= m; ++j) {
int k = 0;
s[k] = 0;
for (int i = 1; i <= n; ++i) {
while (k && p[i][j] <= p[s[k]][j]) {
k--;
}
st[i] = s[k] + 1;
s[++k] = i;
}
k = 0;
s[k] = n + 1;
for (int i = n; i >= 1; --i) {
while (k && p[i][j] <= p[s[k]][j]) {
k--;
}
dr[i] = s[k] - 1;
s[++k] = i;
}
for (int i = 1; i <= n; ++i) {
sol = max(sol, (dr[i] - st[i] + 1) * (p[i][j] * 2 + 1));
}
}
g << sol;
return 0;
}