Pagini recente » Cod sursa (job #2080440) | Cod sursa (job #9812) | Cod sursa (job #1186029) | Cod sursa (job #2472406) | Cod sursa (job #1405223)
#include <fstream>
#include <stack>
using namespace std;
const int kMaxN = 1005;
int N, M, ans;
int a[kMaxN][kMaxN], best[kMaxN][kMaxN];
void Read() {
ifstream fin("dreptpal.in");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= M; ++j)
fin >> a[i][j];
}
void Manacher() {
for (int i = 1; i <= N; ++i) {
int right = 0, mid;
for (int j = 1; j <= M; ++j) {
if (i <= right)
best[i][j] = min(right - j, best[i][mid - (j - mid)]);
while (j - best[i][j] > 1 && j + best[i][j] < M && a[i][j - best[i][j] - 1] == a[i][j + best[i][j] + 1])
++best[i][j];
if (j + best[i][j] > right) {
right = j + best[i][j];
mid = j;
}
}
}
}
void Solve() {
stack<pair<int, int>> st;
for (int i = 1; i <= M; ++i) {
for (int j = 1; j <= N; ++j) {
while (!st.empty() && best[j][i] < st.top().first) {
ans = max(ans, (st.top().first * 2 + 1) * (j - st.top().second));
st.pop();
}
if (st.empty() || best[j][i] > st.top().first)
st.emplace(best[j][i], j);
}
while (!st.empty()) {
ans = max(ans, (st.top().first * 2 + 1) * (N + 1 - st.top().second));
st.pop();
}
}
}
int main() {
Read();
Manacher();
Solve();
ofstream("dreptpal.out") << ans << "\n";
return 0;
}