Pagini recente » Monitorul de evaluare | Profil CarabetRazvan | Rating Black Panda (BangGang) | Cod sursa (job #1152398) | Cod sursa (job #2009586)
#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 - l)]; }
else {
for (l = i; str[r + 1] == str[l - (r - l) - 1]; ++r);
pal[l] = r - l + 1; } }
*/
for (int i = 1, l = -1, r = -1; i <= n; ++i) {
if (r >= i)
pal[i] = min(r - i + 1, pal[l - (i - l)]);
else
pal[i] = 1;
while (str[i - pal[i]] == str[i + pal[i]])
++pal[i];
if (r < i + pal[i] - 1)
l = i, r = i + pal[i] - 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] = -2;
v[n + 1] = -3;
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 * v[i] - 1)); }
fo << ant << endl;
return 0; }