2D prefix sum (2D प्रीफिक्स सम)
एक बड़े 2D ऐरे में, जिसमें संख्याएँ r पंक्तियों और c कॉलम में संगठित हैं, आपको उस मैट्रिक्स का 2D prefix sum (2D प्रीफिक्स सम) निकालना है। किसी स्थान (r, c) पर 2D prefix sum का अर्थ है (0, 0) से लेकर (r, c) तक की सीमाओं के भीतर मौजूद सभी तत्त्वों का योग। दूसरे शब्दों में, यह उस सब-मैट्रिक्स के सभी तत्त्वों का योग है, जिसके कोने (0, 0), (r, 0), (r, c), और (0, c) हैं।
क्या आप इस मैट्रिक्स के प्रत्येक स्थान के लिए 2D prefix sum (2D प्रीफिक्स सम) को प्रभावी ढंग से गणना कर सकते हैं?
+ | + | + | + | |||
+ | + | + | + | |||
+ | + | + | + | |||
+ | + | + | + | |||
इनपुट (Input)
इनपुट की पहली पंक्ति में दो पूर्णांक होते हैं – मैट्रिक्स की पंक्तियों की संख्या r और कॉलमों की संख्या c (1 ≤ r, c ≤ 1000)।
अगली r पंक्तियों में, प्रत्येक में c पूर्णांक होते हैं, जो स्पेस से अलग किए गए हैं और मैट्रिक्स के तत्त्वों का प्रतिनिधित्व करते हैं ।
आउटपुट (Output)
प्रोग्राम को r पंक्तियों में c संख्याएँ प्रिंट करनी चाहिए, जो 2D prefix sum (2D प्रीफिक्स सम) मैट्रिक्स का निरूपण करती हैं।
उदाहरण (Examples)
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