1 条题解

  • 0
    @ 2026-5-7 17:03:59
    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int maxn = 155;
    
    int ans, top;
    char buf[maxn][maxn][maxn];
    int stk[maxn];
    int f[maxn], g[maxn];
    int S[maxn][maxn];
    int a[maxn][maxn][maxn], w[maxn][maxn][maxn];
    
    inline int sum(int x_1, int y_1, int x_2, int y_2){
      int ret = S[x_2][y_2];
      if(x_1)
        ret -= S[x_1 - 1][y_2];
      if(y_1)
        ret -= S[x_2][y_1 - 1];
      if(x_1 && y_1)
        ret += S[x_1 - 1][y_1 - 1];
      return ret;
    }
    
    inline void solve(int p, int q, int r){ // b in r
      for(int k = 0; k < r; ++k){
        for(int i = 0; i < p; ++i){
          for(int j = 0; j < q; ++j){
    	S[i][j] = a[i][j][k];
    	if(i)
    	  S[i][j] += S[i - 1][j];
    	if(j)
    	  S[i][j] += S[i][j - 1];
    	if(i && j)
    	  S[i][j] -= S[i - 1][j - 1];
    	//printf("%d ", a[i][j][k]);
          }
          //puts("");
        }
        //puts("");
        for(int i = 0; i < p; ++i)
          for(int j = 0; j < q; ++j){
    	w[k][i][j] = (j ? w[k][i][j - 1] - 1 : 0), w[k][i][j] = max(w[k][i][j], 0);
    	for(; i + w[k][i][j] < p && j + w[k][i][j] < q && sum(i, j, i + w[k][i][j], j + w[k][i][j]) == (w[k][i][j] + 1) * (w[k][i][j] + 1); ++w[k][i][j]);
    	//printf("k = %d i = %d j = %d w = %d %d\n", k, i, j, w[k][i][j], sum(i, j, i + w[k][i][j], j + w[k][i][j]));
          }
      }
    
      for(int i = 0; i < p; ++i)
        for(int j = 0; j < q; ++j){
          top = 0;
          /*
          for(int k = 0; k < r; ++k)
    	printf("%d ", w[k][i][j]); puts("");
          */
          for(int k = 0; k < r; ++k){
    	for(; top && w[stk[top]][i][j] >= w[k][i][j]; --top);
    	f[k] = (top ? stk[top] : -1);
    	stk[++top] = k;
          }
          top = 0;
          for(int k = r - 1; k >= 0; --k){
    	for(; top && w[stk[top]][i][j] >= w[k][i][j]; --top);
    	g[k] = (top ? stk[top] : r);
    	stk[++top] = k;
          }
          for(int k = 0; k < r; ++k){
    	//printf("k = %d w = %d h = %d  f = %d g = %d\n", k, w[k][i][j], (g[k] - f[k] - 1), f[k], g[k]);
    	ans = max(ans, (g[k] - f[k] - 1) * w[k][i][j]);
          }
        }
      //printf("ans = %d\n", ans);
      return;
    }
    
    int p, q, r;
    
    int main(){
      //freopen("main.in", "r", stdin);
      
      scanf("%d%d%d", &q, &p, &r);
      for(int i = 0; i < p; ++i)
        for(int j = 0; j < q; ++j)
          scanf("%s", buf[i][j]);
    
      for(int i = 0; i < p; ++i)
        for(int j = 0; j < q; ++j)
          for(int k = 0; k < r; ++k)
    	a[i][j][k] = (buf[i][j][k] == 'N');
      solve(p, q, r);
    
      for(int i = 0; i < p; ++i)
        for(int j = 0; j < q; ++j)
          for(int k = 0; k < r; ++k)
    	a[i][k][j] = (buf[i][j][k] == 'N');
      solve(p, r, q);
    
      for(int i = 0; i < p; ++i)
        for(int j = 0; j < q; ++j)
          for(int k = 0; k < r; ++k)
    	a[j][k][i] = (buf[i][j][k] == 'N');
      solve(q, r, p);
    
      printf("%d\n", ans * 4);
      return 0;
    }
    
    • 1

    信息

    ID
    10551
    时间
    8000ms
    内存
    164MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者