Cod sursa(job #2696816)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 16 ianuarie 2021 21:37:12
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>
#define FASTIO fin.tie(0), fout.tie(0), ios::sync_with_stdio(0)
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");

int n, m, mat[1010][1010], npal[1010][1010], maxarea = 1;

void bruteforce_extend(int i, int j, int& centru, int& last) {
	while (last < m && j - (last - j) > 1 && mat[i][j - (last - j) - 1] == mat[i][last + 1])
		last++;
	npal[i][j] = last - j + 1;
	centru = j;
}

void calc_palindromes(int i) {
	int centru = 0, last = 0;
	for (int j = 1; j <= m; j++) {
		if (j > last) {
			bruteforce_extend(i, j, centru, last);
		} else {
			npal[i][j] = min(npal[i][centru - (j - centru)], last - j + 1);
			if (j + npal[i][j] - 1 == last && last < m && j - (last - j) > 1 && mat[i][j - (last - j) - 1] == mat[i][last + 1]) 
				bruteforce_extend(i, j, centru, last);
		}
	}
}

void calc_rectangle(int j) {
	int h[n + 2];
	h[0] = h[n + 1] = 0;
	for (int i = 1; i <= n; i++)
		h[i] = npal[i][j];
	
	int left_max_pos[n + 2];
	left_max_pos[0] = 0;
	int best_pos[n + 2];
	int r = -1;
	best_pos[++r] = 0;
	for (int i = 1; i <= n; i++) {
		while (h[i] < h[best_pos[r]])
			r--;
			
		if (h[i] == h[best_pos[r]]) {
			left_max_pos[i] = left_max_pos[best_pos[r]];
			best_pos[r] = i;
		} else {
			left_max_pos[i] = best_pos[r] + 1;
			best_pos[++r] = i;
		}
	}
	
	int right_max_pos[n + 2];
	right_max_pos[n + 1] = 0;
	r = -1;
	best_pos[++r] = n + 1;
	for (int i = n; i >= 1; i--) {
		while (h[i] < h[best_pos[r]]) 
			r--;
			
		if (h[i] == h[best_pos[r]]) {
			right_max_pos[i] = right_max_pos[best_pos[r]];
			best_pos[r] = i;
		} else {
			right_max_pos[i] = best_pos[r] - 1;
			best_pos[++r] = i;
		}
	}
	
	for (int i = 1; i <= n; i++)
		maxarea = max(maxarea, (2 * h[i] - 1) * (right_max_pos[i] - left_max_pos[i] + 1));
}

int main() {
	//FASTIO;
	fin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			fin >> mat[i][j];
			
	for (int i = 1; i <= n; i++)
		calc_palindromes(i);
			
	for (int j = 1; j <= m; j++)
		calc_rectangle(j);
	
	fout << maxarea;
	return 0;
}