记录编号	97655	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2011] 礼物	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	5.086 s
提交时间	2014-04-19 21:01:56	内存使用	74.52 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<deque>
#include<iomanip>
using namespace std;
const int SIZEN=160;
//1代表完好
void linenext(int g[SIZEN][SIZEN][SIZEN],int X,int Y,int Z,int a[SIZEN][SIZEN][SIZEN]){
	//a应当已经置为空
	for(int i=1;i<=X;i++){
		for(int j=1;j<=Y;j++){
			int k1=1,k2=1;
			while(k1<=Z){
				while(k1<=Z&&!g[i][j][k1]) k1++;
				if(k1>Z) break;
				k2=k1;
				while(k2<=Z&&g[i][j][k2]) k2++;
				for(int t=k1;t<k2;t++) a[i][j][t]=k2-t;
				k1=k2;
			}
		}
	}
}
void maxsquare(int a[SIZEN][SIZEN][SIZEN],int X,int Y,int Z,int s[SIZEN][SIZEN][SIZEN]){
	for(int i=1;i<=X;i++){
		for(int k=1;k<=Z;k++){
			deque<pair<int,int> > Q;
			int j=1,t=1;
			for(int j=1;j<=Y;j++){
				while(j<=Y&&a[i][j][k]==0) j++;
				if(j>Y) break;
				if(t<j) t=j;
				while(t<=Y&&(Q.empty()||(t-j+1<=Q[0].second&&a[i][t][k]>=t-j+1))){
					while(!Q.empty()&&a[i][t][k]<=Q.back().second) Q.pop_back();
					Q.push_back(make_pair(t,a[i][t][k]));
					t++;
				}
				s[i][j][k]=t-j;
				if(!Q.empty()&&Q[0].first==j) Q.pop_front();
			}
		}
	}
}
int a[SIZEN][SIZEN][SIZEN]={0},s[SIZEN][SIZEN][SIZEN]={0};
int getans(int g[SIZEN][SIZEN][SIZEN],int X,int Y,int Z){
	memset(a,0,sizeof(a));
	memset(s,0,sizeof(s));
	linenext(g,X,Y,Z,a);
	maxsquare(a,X,Y,Z,s);
	int ans=0;
	for(int j=1;j<=Y;j++){
		for(int k=1;k<=Z;k++){
			deque<pair<int,int> > Q;
			Q.push_back(make_pair(0,-1));
			int L[SIZEN]={0},R[SIZEN]={0};
			for(int i=1;i<=X;i++){
				while(!Q.empty()&&Q.back().second>=s[i][j][k]) Q.pop_back();
				L[i]=Q.back().first+1;
				Q.push_back(make_pair(i,s[i][j][k]));
			}
			Q.clear();
			Q.push_back(make_pair(X+1,-1));
			for(int i=X;i>=1;i--){
				while(!Q.empty()&&Q.back().second>=s[i][j][k]) Q.pop_back();
				R[i]=Q.back().first-1;
				Q.push_back(make_pair(i,s[i][j][k]));
			}
			for(int i=1;i<=X;i++) ans=max(ans,s[i][j][k]*(R[i]-L[i]+1));
		}
	}
	return ans;
}
int P,Q,R;
int w1[SIZEN][SIZEN][SIZEN]={0},w2[SIZEN][SIZEN][SIZEN]={0},w3[SIZEN][SIZEN][SIZEN]={0};
void work(void){
	int ans=0;
	ans=max(ans,getans(w1,P,Q,R));
	ans=max(ans,getans(w2,Q,P,R));
	ans=max(ans,getans(w3,R,P,Q));
	printf("%d\n",4*ans);
}
void read(void){
	scanf("%d%d%d",&P,&Q,&R);
	string str;
	for(int j=1;j<=Q;j++){
		for(int i=1;i<=P;i++){
			cin>>str;
			for(int k=1;k<=R;k++){
				w1[i][j][k]=w2[j][i][k]=w3[k][i][j]=(str[k-1]=='P'?0:1);
			}
		}
	}
}
int main(){
	freopen("gift.in","r",stdin);
	freopen("gift.out","w",stdout);
	read();
	work();
	return 0;
}