Cod sursa(job #1499699)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 10 octombrie 2015 23:41:18
Problema DreptPal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

template <typename V>
int max_arie_dreptunghi(const int n, V v, const int max_v){
	vector<int> st(n, -1), dr(n, -1);
	vector<vector<int> > poz(max_v+1);
	for(int i = 0; i < n; ++i){
		poz[v(i)].push_back(i); }
	int rez = 0;
	for(int i = max_v; i >= 0; --i){
		for(const auto p : poz[i]){
			st[p] = dr[p] = p;
			if(p > 0 && st[p-1] != -1){
				st[p] = st[p-1]; }
			if(p < n-1 && st[p+1] != -1){
				dr[p] = dr[p+1]; }
			st[dr[p]] = st[p];
			dr[st[p]] = dr[p];
			rez = max(rez, i * (dr[p] - st[p] + 1)); } }
	return rez; }

template <typename S, typename R>
void pscpld(const int n, S str, R rez){
	int centru = -1, poz_dr = -1;
	for(int i = 0; i < n; ++i){
		if(i > poz_dr){
			int j = 1;
			for( ; i-j >= 0 && i+j < n && str(i-j) == str(i+j); ++j);
			--j;
			rez(i) = j;
			if(i+j >= poz_dr){
				centru = i;
				poz_dr = i+j; } }
		else{
			const int val_omolog = rez(2*centru - i);
			if(i+val_omolog < poz_dr){
				rez(i) = val_omolog; }
			else{
				int j = poz_dr - i + 1;
				for( ; i-j >= 0 && i+j < n && str(i-j) == str(i+j); ++j);
				--j;
				rez(i) = j;
				if(i+j >= poz_dr){
					centru = i;
					poz_dr = i+j; } } } } }

int main(){
	ifstream f("dreptpal.in");
	ofstream g("dreptpal.out");
	int n, m;
	f >> n >> m;
	vector<vector<int> > v(n, vector<int>(m, 0)),
		lung_pal(n, vector<int>(m, 0));
	for(auto& x : v){
		for(auto& y : x){
			f >> y; } }
	for(int i = 0; i < n; ++i){
		pscpld(m, [&v, i](const int x){ return v[i][x]; },
			[&lung_pal, i](const int x)->int&{ return lung_pal[i][x]; }); }
	/*
	for(const auto x : lung_pal){
		for(const auto y : x){
			cout << y << ' '; }
		cout << endl; }
	cout << endl;
	*/
	int rez = 0;
	for(int i = 0; i < m; ++i){
		rez = max(rez,
			max_arie_dreptunghi(n,
				[&lung_pal, i](const int x){ return 2*lung_pal[x][i]+1; },
				m)); }
	g << rez;
	return 0; }