सोने की खदानों की रक्षा
वीडियो गेम खेलते समय, संसाधनों का प्रबंधन बेहद महत्वपूर्ण होता है।
अलग-अलग स्थानों पर
n सोने की खदानें हैं। प्रत्येक खदान से एक निश्चित मात्रा में सोना प्राप्त किया जा सकता है। लेकिन इन खदानों को दुश्मनों से बचाना बहुत मेहनत वाला काम है और इसके लिए काफी ऊर्जा की ज़रूरत होती है। अच्छी बात यह है कि हर सोने की खदान से आपको ऊर्जा भी मिल सकती है, क्योंकि प्रत्येक खदान मात्रा में ऊर्जा उत्पन्न करती है।आप चाहते हैं कि आप सोने की खदानों का कोई एक लगातार (contiguous) खंड चुनें और उसे सुरक्षित रखें, ताकि अधिकतम सोना अर्जित किया जा सके। इस खंड का चयन करते समय, आपके पास कम से कम उतनी ऊर्जा होनी चाहिए, जितनी उस खंड की लंबाई हो, ताकि आप दुश्मनों से बचाव कर सकें।
इन खदानों से अधिकतम कितना सोना प्राप्त किया जा सकता है?
इनपुट
इनपुट की पहली पंक्ति में एकल पूर्णांक
n (1 ≤ n ≤ ) दिया होता है।अगली
n पंक्तियों में 3 स्पेस-सेपरेटेड पूर्णांक (1 ≤ ≤ ) होते हैं, जिनमें खदान की निर्देशांक (coordinate), उसकी सोना उत्पादन क्षमता, और उसकी ऊर्जा उत्पादन क्षमता को दर्शाते हैं। सभी निर्देशांक अलग-अलग हैं और बढ़ते क्रम में दिए गए हैं।आउटपुट
कार्यक्रम को सुरक्षित रूप से प्राप्त किए जा सकने वाले अधिकतम सोने की मात्रा को प्रदर्शित करना चाहिए।
उदाहरण
इनपुट | आउटपुट |
4
1 5 1
2 7 2
5 4 1
8 15 1 | 16 |
2
1 4 1
4 5 1 | 5 |
व्याख्या
- पहला उदाहरण → 16
X | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Energy | 1 | 2 | ㅤ | ㅤ | 1 | ㅤ | ㅤ | 1 |
Gold | 5 | 7 | ㅤ | ㅤ | 4 | ㅤ | ㅤ | 15 |
आप शुरुआती 3 खदानें ले सकते हैं ⇒ इस खंड की लंबाई
5-1 = 4 (क्योंकि खदानें कॉर्डिनेट्स के सिरों पर स्थित हैं) और खदानों से उत्पन्न कुल ऊर्जा 1+2+1 = 4 है, जो पर्याप्त है। इस खंड से आपको 5+7+4 = 16 सोना मिलता है।- दूसरा उदाहरण → 5
X | 1 | 2 | 3 | 4 |
Energy | 1 | ㅤ | ㅤ | 1 |
Gold | 4 | ㅤ | ㅤ | 5 |
आप अंतिम सोने की खदान चुन सकते हैं ⇒ इस खंड की लंबाई
0 रहती है, खदान से ऊर्जा 1 मिलती है, और सोना 5 प्राप्त होता है।संकेत 1
Divide & Conquer पद्धति में, बाएँ और दाएँ भागों पर अलग-अलग तकनीकें आज़मानी पड़ सकती हैं।
संकेत 2
मध्य बिंदु से होकर जाने वाले संभावित हलों की गणना करने की कोशिश करें।
Constraints
Time limit: 8 seconds
Memory limit: 512 MB
Output limit: 1 MB