# | 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);
}