Pagini recente » Cod sursa (job #1902012) | Cod sursa (job #2270370) | Cod sursa (job #3254817) | Cod sursa (job #1627553) | Cod sursa (job #2748387)
#include <iostream>
#include <fstream>
#include <vector>
const int NMAX = 1e3;
int a[1 + NMAX];
int manacher[1 + NMAX][1 + NMAX];
int next_left[1 + NMAX][1 + NMAX];
int next_right[1 + NMAX][1 + NMAX];
std::vector<int> stack;
int main() {
std::ifstream in ("dreptpal.in");
std::ofstream out("dreptpal.out");
int n, m;
in >> n >> m;
for (int line = 1; line <= n; ++line) {
for (int i = 1; i <= m; ++i)
in >> a[i];
manacher[line][1] = 1;
int curr = 1;
int best_right = 1;
for (int i = 2; i <= m; ++i) {
int len = 1;
if (i <= best_right)
len = std::min(manacher[line][2 * curr - i], best_right - i + 1);
while (i - len >= 1 && i + len - 1 <= m && a[i + len] == a[i - len]) ++len;
if (i + len - 1 > best_right) {
best_right = i + len - 1;
curr = i;
}
manacher[line][i] = len;
}
}
stack.reserve(n);
for (int col = 1; col <= m; ++col) {
for (int i = 1; i <= n; ++i) {
while (!stack.empty() && manacher[stack.back()][col] >= manacher[i][col])
stack.pop_back();
next_left[i][col] = stack.empty() ? 0 : stack.back();
stack.push_back(i);
}
stack.clear();
for (int i = n; i >= 1; --i) {
while (!stack.empty() && manacher[stack.back()][col] >= manacher[i][col])
stack.pop_back();
next_right[i][col] = stack.empty() ? (n + 1) : stack.back();
stack.push_back(i);
}
stack.clear();
}
int ans = 0;
for (int line = 1; line <= n; ++line) {
for (int i = 1; i <= m; ++i)
ans = std::max(ans, (2 * manacher[line][i] - 1) * (next_right[line][i] - next_left[line][i] - 1));
}
out << ans << '\n';
return 0;
}