Pagini recente » Cod sursa (job #1460044) | Cod sursa (job #2247167) | Istoria paginii utilizator/domnytamaria | Cod sursa (job #1283852) | Cod sursa (job #2009571)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("dreptpal.in");
ofstream fo("dreptpal.out");
const int N = 1024;
int pal[N][N], mx[N][N], st[N], dr[N], v[N];
int n, m;
void manacher(int pal[N], int str[N]) {
for (int i = 1, l = -1, r = -1; i <= m; ++i) {
if (i >= r) {
for (l = r = i; str[r + 1] == str[l - (r - l) - 1]; ++r);
pal[l] = r - l + 1; }
else if (i + pal[l - (i - l)] < r) {
pal[i] = pal[l - (i - 1)]; }
else {
for (l = i; str[r + 1] == str[l - (r - l) - 1]; ++r);
pal[l] = r - l + 1; } } }
int main() {
vector<int> stk;
int ant(1);
fi >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
fi >> mx[i][j];
mx[i][0] = -1;
mx[i][m + 1] = -2; }
for (int i = 1; i <= n; ++i)
manacher(pal[i], mx[i]);
v[0] = -1;
v[n + 1] = -1;
for (int j = 1; j <= m; ++j) {
for (int i = 1; i <= n; ++i)
v[i] = pal[i][j];
stk.push_back(0);
for (int i = 1; i <= n; ++i) {
while (v[stk.back()] >= v[i])
stk.pop_back();
st[i] = stk.back() + 1;
stk.push_back(i); }
stk.clear();
stk.push_back(n + 1);
for (int i = n; i >= 1; --i) {
while (v[stk.back()] >= v[i])
stk.pop_back();
dr[i] = stk.back() - 1;
stk.push_back(i); }
stk.clear();
for (int i = 1; i <= n; ++i)
ant = max(ant, (dr[i] - st[i] + 1) * (2 * pal[i][j] - 1)); }
fo << ant << endl;
return 0; }