2D prefix sum (Somma prefissa 2D)
Dato un grande array 2D di numeri con
r righe e c colonne, ti viene richiesto di calcolare il 2D prefix sum (somma prefissa 2D) di questa matrice. Il 2D prefix sum in una posizione (r, c) rappresenta la somma di tutti gli elementi compresi tra l’angolo (0, 0) e l’elemento (r, c). In altre parole, si tratta della somma degli elementi della sottomatrice con vertici (0, 0), (r, 0), (r, c) e (0, c).Riesci a calcolare in modo efficiente il 2D prefix sum in tutti i punti della matrice?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Input
La prima riga dell’input contiene due interi: il numero di righe nella matrice
r e il numero di colonne c (1 ≤ r, c ≤ 1000).Le successive
r righe contengono c interi separati da uno spazio, che rappresentano gli elementi della matrice .Output
Il programma deve stampare
r righe con c numeri, che rappresentano la matrice del 2D prefix sum.Esempi
Ingresso | Uscita |
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