嘟嘟嘟
正是因为有这样的数据范围，解法才比较暴力。
我们假设取出的长方体常和宽相等，即(a * a * b)。这样我们每次换两条边相等，搞三次就行。
那么对于第(k)层中的第((i, j))点((k, i, j))，求出以这个点为右下角的最大完好的正方形f[k][i][j]。这个可以用倍增求。所以复杂度为(O(n ^ 3 logn))。
然后(O(n ^ 2))枚举平面上的每一个点((x, y))，立体的就是每一竖条，那么对于每一竖条，我们要求的就是(max {(i - j + 1) * (min_{t = j} ^ {i} f[t][x][y]) })。这个求法就是poj 2559了，用单调递增栈(O(n))维护就行。这个的复杂度是(O(n ^ 3))的。
所以总复杂度(O(n ^ 3 logn))。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 155;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int p, q, r;
int _a[3][maxn][maxn][maxn], a[maxn][maxn][maxn];
int sum[maxn][maxn][maxn], f[maxn][maxn][maxn];
In int calc(int k, int i, int j)
{
int L = 1, R = min(i, j);
while(L < R)
{
int mid = (L + R + 1) >> 1;
int Sum = sum[k][i][j] - sum[k][i - mid][j] - sum[k][i][j - mid] + sum[k][i - mid][j - mid];
if(!Sum) L = mid;
else R = mid - 1;
}
return L;
}
struct Node
{
int num, len;
}st[maxn];
In int solve(int p, int q, int r)
{
for(int k = 1; k <= r; ++k)
for(int i = 1; i <= p; ++i)
for(int j = 1; j <= q; ++j)
{
int tp = (a[k][i][j] == 'N' ? 0 : 1);
sum[k][i][j] = sum[k][i - 1][j] + sum[k][i][j - 1] - sum[k][i - 1][j - 1] + tp;
}
for(int k = 1; k <= r; ++k)
for(int i = 1; i <= p; ++i)
for(int j = 1; j <= q; ++j) f[k][i][j] = calc(k, i, j);
int ret = 0, top = 0;
for(int i = 1; i <= p; ++i)
for(int j = 1; j <= q; ++j)
{
top = 0; f[r + 1][i][j] = 0;
for(int k = 1; k <= r + 1; ++k)
{
if(!top || st[top].num < f[k][i][j]) st[++top] = (Node){f[k][i][j], 1};
else
{
int tp = 0;
while(top && st[top].num >= f[k][i][j])
{
ret = max(ret, st[top].num * (st[top].len + tp));
tp += st[top--].len;
}
st[++top] = (Node){f[k][i][j], tp + 1};
}
}
}
return ret;
}
char s[maxn];
int main()
{
p = read(), q = read(), r = read();
for(int j = 1; j <= q; ++j)
for(int i = 1; i <= p; ++i)
{
scanf("%s", s + 1);
for(int k = 1; k <= r; ++k)
_a[0][k][i][j] = _a[1][i][k][j] = _a[2][j][i][k] = s[k];
}
int ans = 0;
memcpy(a, _a[0], sizeof(_a[0]));
ans = max(ans, solve(p, q, r));
memcpy(a, _a[1], sizeof(_a[1]));
ans = max(ans, solve(r, q, p));
memcpy(a, _a[2], sizeof(_a[2]));
ans = max(ans, solve(p, r, q));
write(ans << 2), enter;
return 0;
}