Cod sursa(job #2663477)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 26 octombrie 2020 15:33:50
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

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


vector<int> manacher(vector<int> v){
	int n=v.size();
	vector<int> d(n);
	for(int i=0, l=0, r=-1;i<n;++i){
		int k=(i>r)?1:min(d[l+r-i],r-i+1);
		while(0<=(i-k)&&(i+k<n)&&v[i-k]==v[i+k]) k++;
		d[i]=k--;
		if(i+k>r){
			l=i-k;
			r=i+k;
		}
	}
	return d;
}

int ans=0;

int main(){
	int n, m;
	fin>>n>>m;
	vector<int> sol[n];
	for(int i=0;i<n;++i){
		vector<int> v(m);
		for(int j=0;j<m;++j){
			fin>>v[j];
		}
		sol[i]=manacher(v);
	}
	for(int i=0;i<m;++i){
		stack<int> s;
		int st[n], dr[n];
		for(int j=0;j<n;++j){
			while(!s.empty()&&sol[s.top()][i]>=sol[j][i]) s.pop();
			if(s.empty()) st[j]=0;
			else st[j]=s.top()+1;
			s.push(j);
		}
		while(!s.empty()) s.pop();
		for(int j=n-1;j>=0;--j){
			while(!s.empty()&&sol[s.top()][i]>=sol[j][i]) s.pop();
			if(s.empty()) dr[j]=n-1;
			else dr[j]=s.top()-1;
			s.push(j);
		}
		for(int j=0;j<n;++j){
			int dist=dr[j]-st[j]+1;
			ans=max(ans, dist*(2*sol[j][i]-1));
		}
	}
	fout<<ans<<"\n";
	return 0;
}