Pagini recente » Cod sursa (job #2168720) | Cod sursa (job #1484390) | Cod sursa (job #308648) | Cod sursa (job #1894250) | Cod sursa (job #1970039)
/**
* Worg
*/
#include <stack>
#include <cstdio>
#include <algorithm>
FILE *fin = freopen("dreptpal.in", "r", stdin);
FILE *fout = freopen("dreptpal.out", "w", stdout);
const int kMaxN = 1 + 1000 + 1;
/*-------- Input data --------*/
int N, M;
int mat[kMaxN][kMaxN];
/*-------- Algorithm data --------*/
int manacher[kMaxN][kMaxN];
std::stack<int > stack;
/*-------- --------*/
void ReadInput() {
scanf("%d%d", &N, &M);
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
scanf("%d", &mat[i][j]);
}
}
}
void GetManacher(const int line) {
int center = 0, index = 0;
for(int j = 1; j <= M; j++) {
if(j <= index) {
manacher[line][j] = std::min(index - j + 1, manacher[line][center - (j - center)]);
}
while(j - manacher[line][j] > 0 && j + manacher[line][j] <= M && mat[line][j - manacher[line][j]] == mat[line][j + manacher[line][j]]) {
manacher[line][j] ++;
}
if(j + manacher[line][j] - 1 > index) {
index = j + manacher[line][j] - 1;
center = j;
}
}
}
int GetMaxArea() {
int max_area = 0;
for(int j = 1; j <= M; j++) {
stack.push(0);
for(int i = 1; i <= N + 1; i++) {
while(manacher[i][j] < manacher[stack.top()][j]) { // Nu are sens sa verificam daca stackul este gol
int temp = 2 * manacher[stack.top()][j] - 1; stack.pop();
max_area = std::max(max_area, temp * (i - stack.top() - 1));
}
stack.push(i);
}
while(!stack.empty()) {stack.pop();}
}
return max_area;
}
int main() {
ReadInput();
for(int i = 1; i <= N; i++) {
GetManacher(i);
}
printf("%d\n", GetMaxArea());
return 0;
}