记录编号	175670	评测结果	AAAAAAAAAA
题目名称	[NOI 2005]瑰丽华尔兹	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	1.684 s
提交时间	2015-08-06 17:39:24	内存使用	28.53 MiB

#include<cstdio>
#include<cstring>
#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;

int n,m,t1,t2,t,head,tail,q[210],lenth[210];
int f[210][210][210],tt[210];
int ans=0;
char c[210][210];

void DP1(int x)
{
	
	for(int i=1;i<=m;i++)
	{
		head=1;tail=0;
		for(int j=n;j>=1;j--)
		{
			if(c[j][i-1]=='x'){ head=1,tail=0;continue;}
			while(head<=tail&&q[head]-lenth[x]>j)	head++;
			while(head<=tail&&f[x-1][q[tail]][i]+q[tail]-j<f[x-1][j][i])	tail--;
			q[++tail] = j;
			f[x][j][i]=MAX(f[x-1][q[head]][i]+q[head]-j,f[x][j][i]);
			ans=MAX(f[x][j][i],ans);
		}
	}
}
void DP2(int x)
{
	
	for(int i=1;i<=m;i++)
	{
		head=1;tail=0;
		for(int j=1;j<=n;j++)
		{
			if(c[j][i-1]=='x'){ head=1,tail=0;continue;}
			while(head<=tail&&q[head]+lenth[x]<j)	head++;
			while(head<=tail&&f[x-1][q[tail]][i]+j-q[tail]<f[x-1][j][i])	tail--;
			q[++tail] = j;
			f[x][j][i]=MAX(f[x-1][q[head]][i]+j-q[head],f[x][j][i]);
			ans=MAX(f[x][j][i],ans);
		}
	}
}
void DP3(int x)
{
	
	for(int i=1;i<=n;i++)
	{
		head=1;tail=0;
		for(int j=m;j>=1;j--)
		{
			if(c[i][j-1]=='x'){ head=1,tail=0;continue;}
			while(head<=tail&&q[head]-lenth[x]>j)	head++;
			while(head<=tail&&f[x-1][i][q[tail]]+q[tail]-j<f[x-1][i][j])	tail--;
			q[++tail] = j;
			f[x][i][j]=MAX(f[x-1][i][q[head]]+q[head]-j,f[x][i][j]);
			ans=MAX(f[x][i][j],ans);
		}
	}
}
void DP4(int x)
{
	
	for(int i=1;i<=n;i++)
	{
		head=1;tail=0;
		for(int j=1;j<=m;j++)
		{
			if(c[i][j-1]=='x'){ head=1,tail=0;continue;}
			while(head<=tail&&q[head]+lenth[x]<j)	head++;
			while(head<=tail&&f[x-1][i][q[tail]]+j-q[tail]<f[x-1][i][j])	tail--;
			q[++tail] = j;
			f[x][i][j]=MAX(f[x-1][i][q[head]]+j-q[head],f[x][i][j]);
			ans=MAX(f[x][i][j],ans);
		}
	}
}

int main()
{
    freopen("adv1900.in","r",stdin);
    freopen("adv1900.out","w",stdout);
	memset(f,-0x3f,sizeof(f));
	scanf("%d%d%d%d%d",&n,&m,&t1,&t2,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",c[i]);
	}
	for(int i=1;i<=t;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		lenth[i]=y-x+1;
		scanf("%d",&tt[i]);
	}
	f[0][t1][t2]=0;
	for(int i=1;i<=t;i++)
	{
		if(tt[i]==1)	DP1(i);
		if(tt[i]==2)	DP2(i);
		if(tt[i]==3)	DP3(i);
		if(tt[i]==4)	DP4(i);
	}
	/*for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=m;k++)
			{
				if(f[i][j][k]<0)
					printf("%d ",0);
				else
					printf("%d ",f[i][j][k]);
			}
			printf("\n");
		}
		printf("\n");
	}*/
	printf("%d",ans);
}