Submission #15115

#TimeUsernameProblemLanguageResultExecution timeMemory
15115cki86201빨간 직사각형 (kriii3_QQ)C++98
20 / 20
254 ms45120 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...