2D Prefix-Summe
Angenommen, es gibt ein großes 2D-Array von Zahlen mit
r Zeilen und c Spalten. Ihre Aufgabe ist es, die 2D Prefix-Summe dieser Matrix zu berechnen. Die 2D Prefix-Summe an der Position (r, c) ist die Summe aller Elemente zwischen der Ecke (0, 0) und dem Element (r, c). Anders ausgedrückt handelt es sich um die Summe der Elemente in der Teilmatrix mit den Ecken (0, 0), (r, 0), (r, c) und (0, c).Können Sie die 2D Prefix-Summe für alle Positionen in der Matrix effizient berechnen?
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen – die Anzahl der Zeilen in der Matrix
r und die Anzahl der Spalten c (1 ≤ r, c ≤ 1000).Die nächsten
r Zeilen beinhalten jeweils c ganze Zahlen, die durch ein Leerzeichen getrennt sind und die Elemente der Matrix darstellen .Ausgabe
Das Programm soll
r Zeilen mit jeweils c Zahlen ausgeben, die die 2D Prefix-Summe der Matrix repräsentieren.Beispiele
Eingabe | Ausgabe |
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