2D prefix sum (2D պրեֆիքս գումար)
Ենթադրենք տրված է մեծ երկչափ զանգված, որը պարունակում է
r տող և c սյուն: Ձեզ խնդրում են հաշվել այդ մատրիցի 2D prefix sum-ը (2D պրեֆիքս գումարը) յուրաքանչյուր (r, c) դիրքի համար: 2D prefix sum-ի (2D պրեֆիքս գումարի) արժեքը (r, c) դիրքում սահմանվում է որպես (0, 0) անկյունից մինչև (r, c) տարրն ընդգրկող ուղղանկյան բոլոր արժեքների գումարը: Ավելի հստակ, այն համապատասխանում է այն ենթամատրիցի արժեքների գումարին, որի անկյունները (0, 0), (r, 0), (r, c) և (0, c) են:Կարո՞ղ եք արդյունավետ կերպով հաշվել 2D prefix sum-ը (2D պրեֆիքս գումարը) մատրիցի բոլոր դիրքերի համար:
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
+ | + | + | + | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ | ㅤ |
Մուտք
Մուտքի առաջին տողում տրվում են երկու ամբողջ թվեր - մատրիցի տողերի քանակը
r և սյուների քանակը c (1 ≤ r, c ≤ 1000)։Հաջորդ
r տողերում տրված են c ամբողջ թվեր, որոնք բաժանված են բացատներով և ներկայացնում են մատրիցի տարրերը ։Ելք
Ծրագիրը պետք է տպի
r տող, որոնցից յուրաքանչյուրում կլինեն c թվեր, որոնք ներկայացնում են 2D prefix sum (2D պրեֆիքս գումար) մատրիցը:Օրինակներ
Մուտք | Ելք |
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