HDU 1559 2 Dツリー配列
3910 ワード
転送ドア:HDU 1559
テンプレート問題、注意マトリクスsumツリー配列の和
AC code:
テンプレート問題、注意マトリクスsumツリー配列の和
AC code:
/*adrui's submission
*Language : C++
*Result : Accepted
*File Name: HDU 3333
*Favorite : Dragon Balls
*love : yy
*Standing in the Hall of Fame
*/
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define debug 0
#define inf 0x3f3f3f3f
#define M(a, b) memset(a, b, sizeof(a))
#define lowbit(x) (x & (-x))
const int maxn = 1000 + 5;
int m, n, x, y;
LL c[maxn][maxn];
void add(int x, int y, LL v) {
for (int i = x; i <= m; i += lowbit(i))
for (int j = y; j <= n; j += lowbit(j)) {
c[i][j] += v;
}
}
LL getSum(int x, int y) {
LL res = 0;
for (int i = x; i; i -= lowbit(i))
for (int j = y; j; j -= lowbit(j)) {
res += c[i][j];
}
return res;
}
int main() {
#if debug
freopen("in.txt", "r", stdin);
#endif //debug
cin.tie(0);
cin.sync_with_stdio(false);
int t;
LL a;
cin >> t;
while (t--) {
M(c, 0);
cin >> m >> n >> x >> y;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j) {
cin >> a;
add(i, j, a);
}
LL mx = -inf;
for (int i = x; i <= m; ++i)
for (int j = y; j <= n; ++j) {
LL tmp = getSum(i, j) - getSum(i - x, j) - getSum(i, j - y) + getSum(i - x, j - y);
mx = max(mx, tmp);
}
cout << mx << endl;
}
return 0;
}