Soma prefixo 2D
Dado um grande array 2D de números, com
r linhas e c colunas, o objetivo é calcular a soma prefixo 2D dessa matriz. A soma prefixo 2D numa posição (r, c) corresponde à soma de todos os elementos entre o canto (0, 0) e o elemento (r, c). Em outras palavras, é a soma dos elementos da submatriz delimitada pelos cantos (0, 0), (r, 0), (r, c) e (0, c).Consegue calcular de forma eficiente a soma prefixo 2D para todos os elementos da matriz?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Entrada
A primeira linha da entrada contém dois inteiros – o número de linhas da matriz
r e o número de colunas c (1 ≤ r, c ≤ 1000).Nas
r linhas seguintes, são apresentados c inteiros separados por espaço, que representam os elementos da matriz .Saída
O programa deve imprimir
r linhas, cada uma contendo c valores que representam a matriz de soma prefixo 2D.Exemplos
Entrada | Saída |
3 5
1 2 -3 4 6
-1 3 8 4 0
0 1 -2 0 5 | 1 3 0 4 10
0 5 10 18 24
0 6 9 17 28 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 15 MB