2D prefix sum
大きな2次元配列（r 行と c 列の数値要素）を与えられたとき、各要素に対する二次元累積和 (2D prefix sum) を求めることが課題です。ここで、二次元累積和とは、座標 (0, 0) から (r, c) までの要素をすべて合計したもので、それは四隅 (0, 0), (r, 0), (r, c), (0, c) で区切られる部分行列の要素合計を指します。
行列のすべての位置に対して、この二次元累積和を効率的に計算できるでしょうか？
+ | + | + | + | |||
+ | + | + | + | |||
+ | + | + | + | |||
+ | + | + | + | |||
入力
入力の最初の行には、行列の行数 r と列数 c の2つの整数が与えられます (1 ≤ r, c ≤ 1000)。
続く r 行には、それぞれ c 個の整数が空白区切りで与えられます。これらは行列の要素を表します ()。
出力
プログラムは、二次元累積和行列を表す c 個の数値を含む r 行を出力してください。
例
入力 | 出力 |
|---|---|
3 5 | 1 3 0 4 10 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB