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;
}

Download