نسي Farmer John إصلاح ثقب في سياج المزرعة، فهربت أبقاره $N$ $(1 \le N \le 1,000)$ وأخذت تعيث فسادًا! كل دقيقة تقضيها بقرة خارج السياج تسبب ضررًا بدولار واحد. يجب أن يزور FJ كل بقرة ويضع لها رسنًا يهدئها ويوقف الضرر.
لحسن الحظ توجد الأبقار في مواضع مختلفة على خط مستقيم بطريق خارج المزرعة. يعرف FJ موضع $P_i$ لكل بقرة $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ بالنسبة للبوابة (الموضع 0) التي يبدأ منها.
يتحرك FJ وحدة مسافة واحدة في الدقيقة ويضع الرسن فورًا. حدد ترتيب الزيارات الذي يصغّر مجموع تكاليف الضرر، واحسب أقل مجموع ممكن.
الإدخال
- السطر 1: عدد الأبقار $N$.
- الأسطر $2\ldots N+1$: يحتوي السطر $i+1$ على العدد الصحيح $P_i$.
الإخراج
- السطر 1: أقل مجموع لتكاليف الضرر.
أمثلة
الإدخال 1
4 -2 -12 3 7
الإخراج 1
50
ملاحظة
الأبقار الأربع في المواضع $-2$ و$-12$ و$3$ و$7$.
الترتيب الأمثل $-2,3,7,-12$. يصل FJ إلى $-2$ في دقيقتين، فيكون ضرر تلك البقرة دولارين.
ثم يذهب إلى $3$ (المسافة 5)، فيكون ضرر تلك البقرة المتراكم $2 + 5 = 7$ دولارات.
يقضي 4 دقائق أخرى للوصول إلى $7$، بضرر $7 + 4 = 11$ دولارًا لتلك البقرة.
أخيرًا يقضي 19 دقيقة للوصول إلى $-12$، بتكلفة $11 + 19 = 30$ دولارًا.
الضرر الإجمالي $2 + 7 + 11 + 30 = 50$ دولارًا.
مؤلف المسألة: Chris Tzamos, 2006