कैट गूज और रैंडम मैट्रिक्स
Problem
<दिव>
कैट गूज निक फ्यूरी के लिए \(n \cdot m\) आकार की एक आयताकार टेबल तैयार करता है जिसमें 0< के अंक होते हैं। /span> code> से p−1. निक फ्यूरी को तुरंत एहसास हुआ कि इस तालिका में प्रत्येक संख्या 0 से p− 1 , दूसरों की परवाह किए बिना।
आपका कार्य — इस तालिका का एक आयताकार सबमैट्रिक्स खोजें, जिसमें योग p से विभाज्य हो। ऐसे सभी सबमैट्रिसेस में, आपको वह ढूंढना होगा जिसमें तत्वों का योग अधिकतम हो।
औपचारिक रूप से, आपको खोजने की आवश्यकता है
\(1 <= i_1 <= i_2 <= n\),
\( 1 <= j_1 <= j_2 <= m\) कि
ax,y समस्त
\(i_1 <= x <= i_2\),
\(j_1 <= y <= j_2\) p पर विभाजित, और इनमें से अधिकतम राशि है।
इनपुट
पहली पंक्ति में तीन पूर्णांक होते हैं n, m, p (\(1 <) ;= n m, p <= 1,000,000\)) — मैट्रिक्स के आयाम और वह संख्या जिससे सबमैट्रिक्स के योग को विभाजित किया जाना चाहिए।
निम्न n पंक्तियों में m पूर्णांक होते हैं, j-th संख्या i-th पंक्ति में बराबर ).
यह गारंटी है कि a में प्रत्येक संख्या यादृच्छिक रूप से स्वतंत्र रूप से चुनी जाती है, संभवतः 0 से p−1 तक।
आउटपुट
एक पूर्णांक प्रिंट करें — एक आयताकार सबमैट्रिक्स का अधिकतम योग जहां योग p से विभाज्य है। यदि कोई नहीं है, तो 0 प्रिंट करें।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
65 |