1 条题解
-
0
#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
- 上传者