# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
15053 | 2015-07-11T07:46:09 Z | myungwoo | 빨간 직사각형 (kriii3_QQ) | C++14 | 0 ms | 0 KB |
#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); }