oj.uz

Submission #15153

# Submission time Handle Problem Language Result Execution time Memory
15153 2015-07-11T23:13:35 Z ggoh 빨간 직사각형 (kriii3_QQ) C++
0 / 20
 0 ms 44520 KB 
#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);
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 44520 KB Output is correct
2 Incorrect 0 ms 44520 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -