P4147「玉蟾宫」

5 6 
R F F F F F 
F F F F F F 
R R R F F F 
F F F F F F 
F F F F F F

45

#include <bits/stdc++.h>
#define ll int
#define MAXN 1005
using namespace std;

// 矩形统计图
struct RC {
    ll i;
    ll v;
    RC():i(0), v(0) {}
    RC(ll _i, ll _v): i(_i), v(_v) {}
};


// 计算最大子矩阵面积
ll maxRectangle(ll *A, ll n) {
    ll ans = 0;
    ll depth = 0;
    RC stack[MAXN];
    stack[depth] = RC(-1,-1);
    for(ll i = 0; i < n; ++i) {
        RC t(i,A[i]);
        ll sdepth = depth;
        while(depth && stack[depth].v >= A[i]) {
            ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
            --depth;  
        }
        stack[++depth] = t;
    }
    ll sdepth = depth;
    while(depth) {
        ans = max(ans, (stack[sdepth].i-stack[depth-1].i)*stack[depth].v);
        --depth; 
    }
    return ans;
}

int main()
{
    ll n, m;
    ll a[MAXN][MAXN], b[MAXN][MAXN];
    scanf("%d%d", &n, &m);
    for(ll i = 0; i < n; ++i) {
        for(ll j = 0; j < m; ++j) {
            char str[2];
            scanf("%s", str);
            if(str[0] == 'R') {
                a[i][j] = 0;
            } else {
                a[i][j] = 1;
            }
        }
    }
    for(ll j = 0; j < m; ++j)  b[0][j] = a[0][j];
    for(ll i = 1; i < n; ++i) {
        for(ll j = 0; j < m; ++j) {
            if(a[i][j]) {
                b[i][j] = b[i-1][j] + 1;
            } else {
                b[i][j] = 0;
            }
        }
    }
    ll ans = 0;
    for(ll i = 0; i < n; ++i) {
        ans = max(ans, maxRectangle(b[i], m));
    }
    printf("%d\n", 3*ans);
    return 0;
}