제출 #15054

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15054		myungwoo	빨간 직사각형 (kriii3_QQ)	C++14	20 / 20	264 ms	10532 KiB

qq

#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++) scanf("%s", 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);
}

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