Submission #15153

#TimeUsernameProblemLanguageResultExecution timeMemory
15153ggoh빨간 직사각형 (kriii3_QQ)C++98
0 / 20
0 ms44520 KiB
#include<cstdio>
#include<algorithm>
#include<cstring>
int a,b,i,j,S,sum,p,u,q,w[3333][3333];
int P[3333],Q[3333],max[3333];
char s[3333];
main()
{
	scanf("%d%d",&a,&b);
	for(i=1;i<=a;i++)
	{
		scanf("%s",s);
		for(j=0;j<b;j++)
		{
			if(s[j]=='R')w[i][j+1]=1;
		}
	}
	for(i=1;i<=a;i++)
	{
		p=0;
		q=0;
		sum=0;
		for(j=1;j<=b;j++)
		{
			if(w[i][j]==0)
			{
				S+=i*j;
				max[j]=i;
				P[p++]=i;
				Q[q++]=j;
				sum=j*i;
			}
			else
			{
				while(max[j]>P[p-1]&&p>0)
				{
					p--;
					q--;
				}
				u=q>0?Q[q-1]:0;
				sum+=(j-u)*max[j];
				P[p++]=max[j];
				Q[q++]=j;
				S+=sum;
			}
		}
	}
	printf("%d",a*(a+1)/2*b*(b+1)/2-S);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...