제출 #15156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15156		ggoh	빨간 직사각형 (kriii3_QQ)	C++98	20 / 20	225 ms	87952 KiB

qq

#include<cstdio>
#include<algorithm>
#include<cstring>
long long a,b,i,j,S,sum,p,u,q,w[3333][3333];
long long P[3333],Q[3333],max[3333];
char s[3333];
main()
{
	scanf("%lld%lld",&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)
				{
					u=q>1?Q[q-2]:0;
					sum-=(Q[q-1]-u)*P[p-1];
					p--;
					q--;
				}
				u=q>0?Q[q-1]:0;
				sum+=(j-u)*max[j];
				P[p++]=max[j];
				Q[q++]=j;
				S+=sum;
			}
		}
	}
	printf("%lld",a*(a+1)/2*b*(b+1)/2-S);
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10