Module: الأنماط في البرمجة الديناميكية


Problem

6 /7


الأولمبياد الأقاليمي

Problem

في الأولمبياد الأقاليمي لبرمجة الروبوت ، تقام المسابقات في جولة واحدة وبصيغة غير عادية. تُعطى المهام للمشاركين بالتسلسل ، وليس كلها في بداية الجولة ، وكل مهمة من الدرجة الأولى (1 & le؛ i & le؛ n) تصبح متاحة للمشاركين في وقتها i . عند استلام المهمة التالية ، يجب على كل مشارك أن يحدد على الفور ما إذا كان سيحلها أم لا. إذا اختار حل هذه المشكلة ، فسيكون أمامه t i دقيقة لإرسال الحل للتحقق ، وخلال هذا الوقت لا يمكنه التبديل إلى حل مشكلة أخرى. إذا رفض المشارك حل هذه المشكلة ، فلن يتمكن في المستقبل من العودة إليها. في الوقت الذي انتهى فيه الوقت المخصص للمهمة التي يقوم المشارك بحلها ، يمكنه البدء في حل مهمة أخرى أصبحت متاحة في نفس اللحظة ، إذا كانت هناك مثل هذه المهمة ، أو الانتظار حتى تظهر مهمة أخرى. في الوقت نفسه ، من أجل الحل الصحيح لمشكلة i ، يتلقى المشارك c i نقاط.

أرتور ، الذي يمثل أحد مراكز الذكاء الاصطناعي الإقليمية في الأولمبياد الأقاليمي ، يدرك أنه ليس فقط القدرة على حل المشكلات ، ولكن أيضًا الحساب الاستراتيجي الصحيح للمشكلات التي يجب حلها وأيها يجب تخطيه ، يلعب دورًا مهمًا في مثل الأولمبياد. إنه ، مثل جميع المشاركين ، يعرف قبل بدء الجولة في أي وقت ستصبح كل مهمة متاحة ، ومقدار الوقت الذي سيتم تخصيصه لحلها وعدد النقاط التي يمكنك الحصول عليها لحلها. أرتور طالب موهوب ، وبالتالي سيكون قادرًا على حل أي مشكلة يختار حلها في الأولمبياد بنجاح في الوقت المحدد وتمرير التحقق.

مطلوب كتابة برنامج يحدد الحد الأقصى لعدد النقاط التي يمكن أن يحصل عليها آرثر من خلال الاختيار الأمثل للمشكلات التي سيحلها ، بالإضافة إلى عدد وقائمة هذه المشكلات.

إدخال
يحتوي السطر الأول على عدد صحيح واحد n (1 & le؛ n & le؛ 10 5 ) عدد المشكلات في الأولمبياد.

تحتوي الأسطر n التالية على أوصاف للمشكلات ، وثلاثة أرقام في كل سطر: si لحظة ظهور المشكلة i بالدقائق ، t i الوقت المخصص لحلها بالدقائق ، و ci كم عدد النقاط التي سيحصل عليها المشارك لحل هذه المشكلة (1 & le؛ s i ، t i ، c i & le؛ 10 9 < / sup>).

بصمة
الخط الأول نبسب ؛ يجب أن يحتوي على رقم واحد & ndash؛ أقصى عدد من النقاط يمكن أن يحصل عليها آرثر في الأولمبياد.

يجب أن يحتوي السطر الثاني على عدد صحيح واحد م - عدد المهام التي سيتم حلها مع الاختيار الأمثل.

يجب أن يحتوي السطر الثالث على m أعداد صحيحة مفصولة بمسافات - أعداد هذه المشاكل بالترتيب الذي تم حلها به. المهام مرقمة ، بدءًا من واحد ، بالترتيب الموصوف في ملف الإدخال.

إذا كان هناك العديد من الإجابات المثلى ، فقم بطباعة أي منها.
أمثلة <الجسم>
# إدخال الإخراج
1 2
1 1 1
2 2 2 		3
2
1 2
2 3
1 2 1
3 2 1
2 4 3 		3
1
3

time 2000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!