Pagini recente » Cod sursa (job #2744887) | Cod sursa (job #2739051) | Cod sursa (job #2450059) | Cod sursa (job #978907) | Cod sursa (job #1226699)
#include <fstream>
#include <stack>
#define DIM 1005
using namespace std;
ifstream f("dreptpal.in");
ofstream g("dreptpal.out");
int n, m;
int A[DIM][DIM], P[DIM][DIM];
stack<int> s;
inline int maxim(int x, int y) {
return ( x>y ? x : y );
}
inline int minim(int x, int y) {
return (x<y ? x : y);
}
int main() {
f >> m >> n;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
f >> A[i][j];
//MANACHER
for (int i = 1; i <= m; ++i) {
int R = 0, C = 0;
for (int j = 1; j <= n - 1; ++j) {
int j_mirror = 2 * C - j;
P[i][j] = R > j ? minim(R - j, P[i][j_mirror]) : 0;
while (j - P[i][j] - 1 > 0 && A[i][j - P[i][j] - 1] == A[i][j + P[i][j] + 1])
++P[i][j];
if (R < j + P[i][j]) {
R = j + P[i][j];
C = j;
}
}
}
int L, R;
int SOL = 0;
for (int j = 1; j <= n; ++j) {
while (!s.empty())
s.pop();
for (int i = 1; i <= m + 1; ++i) {
while (!s.empty() && P[i][j] <= P[s.top()][j]) {
int head = s.top();
s.pop();
if (s.empty())
L = 1;
else
L = s.top() + 1;
R = i - 1;
SOL = maxim(SOL, (R - L + 1)*(P[head][j]*2 + 1));
}
s.push(i);
}
}
g << SOL;
return 0;
}