MAXCUB - Khối lập phương lớn nhất
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
#define N 31
int a[N][N][N], f[N][N][N], n;
void enter() {
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
scanf("%d", &a[i][j][k]);
}
inline int subRectangular(int a, int b, int c, int x, int y, int z) {
return f[x][y][z] - f[a-1][y][z] - f[x][y][c-1] - f[x][b-1][z] + f[x][b-1][c-1]
+ f[a-1][y][c-1] + f[a-1][b-1][z] - f[a-1][b-1][c-1];
}
void dp() {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
f[i][j][k] = f[i-1][j][k] + f[i][j][k-1] + f[i][j-1][k] - f[i][j-1][k-1]
- f[i-1][j][k-1] - f[i-1][j-1][k] + f[i-1][j-1][k-1] + a[i][j][k];
}
int maxCub() {
int res = INT_MIN;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= n; ++k)
for(int sz = min(i, min(j, k)); sz > 0; --sz)
res = max(res, subRectangular(i-sz+1,j-sz+1,k-sz+1,i,j,k));
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
int tc; scanf("%d", &tc);
while(tc--) {
enter();
dp();
printf("%d\n", maxCub());
}
return 0;
}