Cod sursa(job #1970039)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 18 aprilie 2017 20:25:54
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
/**
  *  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;
}