Pagini recente » Cod sursa (job #2701376) | Cod sursa (job #2608450) | Cod sursa (job #1125596) | Cod sursa (job #1045262) | Cod sursa (job #1156447)
#include <fstream>
#include <stack>
using namespace std;
const int MAX_N = 1002;
int N, M, sol;
int A[MAX_N][MAX_N], D[MAX_N][MAX_N];
void Manacher(int n, int v[], int d[]) {
for(int i = 1, C = 0, R = 0; i <= n; ++i) {
if(R >= i) {
int i_mirror = 2 * C - i;
d[i] = min(d[i_mirror], R - i);
}
while(i - d[i] - 1 >= 1 && i + d[i] + 1 <= n && v[i - d[i] - 1] == v[i + d[i] + 1])
++d[i];
if(i + d[i] > R)
C = i, R = i + d[i];
}
for(int i = 1; i <= n; ++i)
d[i] = 2 * d[i] + 1;
}
int solveLine(int n, int v[]) {
stack < int > st;
int L[MAX_N], R[MAX_N];
for(int i = 0; i < MAX_N; ++i)
L[i] = R[i] = 0;
for(int i = 1; i <= n; ++i) {
while(!st.empty() && v[i] <= v[st.top()])
st.pop();
if(!st.empty())
L[i] = st.top();
st.push(i);
}
while(!st.empty())
st.pop();
for(int i = n; i >= 1; --i) {
while(!st.empty() && v[i] <= v[st.top()])
st.pop();
if(!st.empty())
R[i] = st.top();
st.push(i);
}
int ret = 0;
for(int i = 1; i <= n; ++i)
ret = max(ret, v[i] * (R[i] - L[i] - 1));
return ret;
}
int main() {
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
f >> N >> M;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
f >> A[i][j];
for(int i = 1; i <= N; ++i)
Manacher(M, A[i], D[i]);
int temp[MAX_N];
for(int j = 1; j <= M; ++j) {
for(int i = 1; i <= N; ++i)
temp[i] = D[i][j];
sol = max(sol, solveLine(N, temp));
}
g << sol << "\n";
f.close();
g.close();
return 0;
}