嘟嘟嘟



正是因为有这样的数据范围，解法才比较暴力。



我们假设取出的长方体常和宽相等，即\(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;

}