Pagini recente » Cod sursa (job #867380) | Cod sursa (job #1428203) | Cod sursa (job #1141089) | Cod sursa (job #2765924) | Cod sursa (job #2798890)
#include <bits/stdc++.h>
using namespace std;
ifstream in("dreptpal.in");
ofstream out("dreptpal.out");
const int INF = (int)1e5;
int solve(vector<int> &hist) {
int maxArea = 0;
hist.push_back(-INF);
stack<int> st;
for (int i = 0; i < (int)hist.size(); i++) {
while ((int)st.size() > 0 && hist[st.top()] > hist[i]) {
int l = st.top();
st.pop();
int area;
if ((int)st.size() > 0)
area = (i - l - 1) * hist[l];
else
area = i * hist[l];
maxArea = max(maxArea, area);
}
st.push(i);
}
return maxArea;
}
int main() {
in.tie(NULL);
out.tie(NULL);
ios_base::sync_with_stdio(false);
int n, m; in >> n >> m;
vector<vector<int>> p;
for (int i = 0; i < n; i++) {
vector<int> s(m);
for (int &x : s)
in >> x;
vector<int> pal(m);
int l = -1, r = -1;
for (int j = 0; j < m; j++) {
if (j > r)
pal[j] = 1;
else
pal[j] = min(pal[l + r - j], r - j + 1);
while (j - pal[j] >= 0 && j + pal[j] < m && s[pal[j] + j] == s[j - pal[j]])
pal[j]++;
pal[j]--;
if (j + pal[j] > r) {
r = j + pal[j];
l = j - pal[j];
}
}
p.push_back(pal);
}
for (auto &row : p)
for (int &x : row)
x += x + 1;
int ans = 1;
for (int j = 0; j < m; j++) {
vector<int> cand;
for (int i = 0; i < n; i++)
cand.push_back(p[i][j]);
ans = max(ans, solve(cand));
}
out << ans << "\n";
return 0;
}