ऐरे को कम से कम अधिकतम योग के साथ विभाजित करना
आपको
n पूर्णांक दिए गए हैं और एक पूर्णांक k भी दिया गया है। आपका काम है कि आप पूरे ऐरे को k निरंतर (contiguous) हिस्सों में इस तरह बाँटें कि किसी भी उप-ऐरे (subarray) का अधिकतम योग यथासंभव कम हो सके।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (1 ≤ n ≤ ) और k (1 ≤ k ≤ n) दिए होते हैं।दूसरी पंक्ति में स्पेस से अलग किए हुए
n पूर्णांक होते हैं, जहाँ प्रत्येक की सीमा ≤ ≤ है।आउटपुट
कार्यक्रम को वह अधिकतम उप-ऐरे योग प्रिंट करना चाहिए, जो संभवतः सबसे छोटा हो।
Examples
Input | Output |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
Explanation
[1 2 3] [6 2]⇒ अधिकतम उप-ऐरे योग 6 + 2 = 8
[1 2] [10] [3 2]⇒ अधिकतम उप-ऐरे योग 10
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB