제출 #15160

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

qq

#include<cstdio>

char a[3333][3333];
int d[3333][3333];
int s[3333],p[3333],sn;

int main()
{
    long long r=0;
    int i,j,n,m,t;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
        for(j=1;j<=m;j++)
        {
            d[i][j]=d[i][j-1]+1;
            if(a[i][j]=='B')d[i][j]=0;
        }
    }
    for(j=1;j<=m;j++)
    {
        sn=t=0;
        s[sn]=0;
        p[sn]=0;
        sn++;
        for(i=1;i<=n;i++)
        {
            while(sn>=2&&s[sn-1]>d[i][j])
            {
                t-=s[sn-1]*(p[sn-1]-p[sn-2]);
                sn--;
            }
            t+=d[i][j]*(i-p[sn-1]);
            s[sn]=d[i][j];
            p[sn]=i;
            sn++;
            r+=t;
        }
    }
    printf("%lld",r);
}

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