Submission #15115

#	Time	Username	Problem	Language	Result	Execution time	Memory
15115		cki86201	빨간 직사각형 (kriii3_QQ)	C++98	20 / 20	254 ms	45120 KiB

qq

#include<stdio.h>

char p[3002][3002];
int c[3002][3002], s[3002][2], d[3002];
long long ans;

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)scanf("%s", p[i]+1);
	for (int i = 1; i <= n; i++){
		for (int j = 1, now = 0; j <= m; j++){
			if (p[i][j] == 'R')c[i][j] = ++now;
			else now = 0;
		}
	}
	for (int i = 1; i <= m; i++){
		for (int j = 1, top = 0; j <= n + 1; j++){
			while (top && s[top - 1][1] >= c[j][i])--top;
			if (top)d[j] = d[s[top - 1][0]] + (j - s[top - 1][0]) * c[j][i];
			else d[j] = c[j][i] * j;
			s[top][0] = j, s[top++][1] = c[j][i];
			ans += d[j];
		}
	}
	printf("%lld", ans);
	return 0;
}

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