2D prefix sum (Suma prefijo 2D)
Dado un gran arreglo 2D de números con
r filas y c columnas, se te pide calcular la 2D prefix sum (suma prefijo 2D) de esa matriz. La 2D prefix sum en la posición (r, c) es la suma de todos los elementos comprendidos entre la esquina (0, 0) y el elemento (r, c). En otras palabras, es la suma de los elementos del submatriz que tiene como esquinas (0, 0), (r, 0), (r, c) y (0, c).¿Puedes calcular de manera eficiente la 2D prefix sum para todas las posiciones de la matriz?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Entrada
La primera línea de la entrada contiene dos enteros: el número de filas de la matriz
r y el número de columnas c (1 ≤ r, c ≤ 1000).Las siguientes
r líneas contienen c números enteros separados por un espacio, que representan los elementos de la matriz .Salida
El programa debe imprimir
r líneas que contengan c números, los cuales representan la matriz de 2D prefix sum.Ejemplos
Input | Output |
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