【二次元累積和】 二次元累積和 7
(paizaランク C 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
1 行目に整数 N, M, Q が与えられます。
2 行目以降に N 行 M 列の整数の二次元配列 A が与えられます。
2 + N 行目以降に Q 行に渡って整数 a_i, b_i, c_i, d_i (0 ≦ i ≦ Q - 1) が与えられます。
A の j 行目 k 列目を A_{j, k} (0 ≦ j ≦ N - 1, 0 ≦ k ≦ M - 1) と表すことにします。
i 番目の長方形領域の左上の要素を A_{a_i, b_i}, 右下の要素を A_{c_i, d_i} としたとき、これら Q 個の長方形領域内の整数の和を累積和を用いて求め、改行区切りで出力してください。
- 入力される値
-
1 行目に整数 N, M, Q が与えられます。
2 行目以降に N 行 M 列の整数の二次元配列 A が与えられます。
2 + N 行目以降に Q 行に渡って整数 a_i, b_i, c_i, d_i (0 ≦ i ≦ Q - 1) が与えられます。
N M Q
A_{0, 0} A_{0, 1} ... A_{0, M - 1}
A_{1, 0} A_{1, 1} ... A_{1, M - 1}
...
A_{N - 1, 0} A_{N - 1, 1} ... A_{N - 1, M - 1}
a_0 b_0 c_0 d_0
a_1 b_1 c_1 d_1
...
a_{Q - 1} b_{Q - 1} c_{Q - 1} d_{Q - 1}
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
i 番目の長方形領域の左上の要素を A_{a_i, b_i}, 右下の要素を A_{c_i, d_i} としたとき、これら Q 個の長方形領域内の整数の和を累積和を用いて求め、改行区切りで出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N, M, Q ≦ 10
・ 1 ≦ A_{i, j} ≦ 100 (0 ≦ i ≦ N - 1, 0 ≦ j ≦ M - 1)
・ 0 ≦ a_i ≦ c_i ≦ N - 1 (0 ≦ i ≦ Q - 1)
・ 0 ≦ b_i ≦ d_i ≦ M - 1 (0 ≦ i ≦ Q - 1)
- 入力例1
-
5 5 3
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
1 1 3 3
2 2 4 4
0 0 2 2
- 出力例1
-
45
63
27
- 入力例2
-
8 3 1
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
3 1 8
8 1 3
1 3 8
0 0 7 2
- 出力例2
-
96
