| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 15053 | myungwoo | 빨간 직사각형 (kriii3_QQ) | C++14 | 0 ms | 0 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
typedef long long lld;
typedef pair<int, int> pii;
int N, M;
int H[3001];
char A[3001][3002];
int main()
{
	scanf("%d%d ", &N, &M);
	for (int i=1;i<=N;i++) gets(A[i]+1);
	lld ans = 0;
	for (int i=1;i<=N;i++){
		stack <pii> stk;
		stk.push(mp(-1, 0));
		lld val = 0;
		for (int j=1;j<=M;j++){
			H[j] = A[i][j] == 'R' ? H[j] + 1 : 0;
			while (!stk.empty() && stk.top().first >= H[j]){
				int h = stk.top().first, x2 = stk.top().second;
				stk.pop();
				int x1 = stk.top().second;
				val -= (x2-x1) * h;
			}
			val += H[j] * (j - stk.top().second);
			stk.push(mp(H[j], j));
			ans += val;
		}
	}
	printf("%lld\n", ans);
}
