UVA - 10755 Garbage Heap
3600 ワード
3 Dマトリクス、サブマトリクス、最大値を与えます.
解題構想:各平面上のマトリクスをマトリクス和に記録し、2次元上のマトリクスを列挙し、3次元にマッピングすることができる.
解題構想:各平面上のマトリクスをマトリクス和に記録し、2次元上のマトリクスを列挙し、3次元にマッピングすることができる.
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int T;
scanf("%d", &T);
while (T--) {
int A, B, C;
long long tmp, s[25][25][25] = {0};
scanf("%d%d%d", &A, &B, &C);
for (int i = 1; i <= A; i++)
for (int j = 1; j <= B; j++)
for (int k = 1; k <= C; k++) {
scanf("%lld", &tmp);
s[i][j][k] = s[i][j][k-1] + s[i][j-1][k] - s[i][j-1][k-1] + tmp;
}
long long ans = -0x3f3f3f3f3f3f3f;
for (int m = 1; m <= B; m++)
for (int n = m; n <= B; n++)
for (int p = 1; p <= C; p++)
for (int q = p; q <= C; q++) {
long long MAX = 0;
for (int x = 1; x <= A; x++) {
long long sum = s[x][n][q] - s[x][m-1][q] - s[x][n][p-1] + s[x][m-1][p-1];
MAX = max(MAX + sum, sum);
ans = max(ans, MAX);
}
}
printf("%lld
", ans);
if (T) printf("
");
}
return 0;
}