أُعطيت تسلسلين من الأعداد الصحيحة، طول كل منهما $n$: $B=[b_1,\ldots,b_n]$ و$C=[c_1,\ldots,c_n]$. لكل تسلسل أعداد صحيحة غير سالبة $D=[d_1,\ldots,d_n]$ طوله $n$، لتكن $S(D)$ مجموعة جميع الفهارس $i$ التي تحقق $d_i=0$. نعرّف $f(D)=\sum_{i\in S(D)}b_i$ و$g(D)=\prod_{i\in S(D)}c_i$. وتحديداً، إذا كانت $S(D)$ فارغة، فإن $f(D)=0$ و$g(D)=1$.
لدى 小 L تسلسل من الأعداد الصحيحة الموجبة $A=[a_1,\ldots,a_n]$ طوله $n$. يستطيع 小 L تعديل $A$ كما يلي:
- يختار فهرسين متجاورين $i,j$ في التسلسل $A$، أي $1\leq i,j\leq n$ و$|i-j|=1$. إذا كان $a_i\leq a_j$، يغيّر $a_j$ إلى $a_j-a_i$، وفي الوقت نفسه يغيّر $a_i$ إلى $0$.
يمكن لـ 小 L إجراء أي عدد من عمليات التعديل، أو عدم إجراء أي تعديل. يريد، عبر جميع التسلسلات $D$ التي يمكن الحصول عليها من $A$ بهذه العمليات، إيجاد أكبر قيمة لـ $f(D)$ ومجموع قيم $g(D)$. ساعده في حساب هاتين القيمتين. وبصياغة رسمية، لتكن $T(A)$ مجموعة جميع التسلسلات التي يمكن الحصول عليها من $A$ بالعمليات السابقة؛ المطلوب حساب $\max_{D\in T(A)}f(D)$ و$\sum_{D\in T(A)}g(D)$. ولأن $\sum_{D\in T(A)}g(D)$ قد تكون كبيرة، يكفي حسابها بترديد $1\,000\,000\,007$.
الإدخال
تُقرأ البيانات من الملف sequence.in.
تحتوي هذه المسألة على عدة مجموعات بيانات اختبار.
يحتوي السطر الأول من الإدخال على عددين صحيحين غير سالبين $c,t$، يمثّلان رقم حالة الاختبار وعدد مجموعات البيانات على الترتيب. وتعني $c=0$ أن حالة الاختبار مثال.
تلي ذلك مجموعات البيانات بالتتابع. لكل مجموعة:
يحتوي السطر الأول على عدد صحيح موجب $n$، يمثّل طول التسلسل.
يحتوي السطر الثاني على $n$ عدداً صحيحاً موجباً $a_1,\ldots,a_n$، تمثّل التسلسل $A$.
يحتوي السطر الثالث على $n$ عدداً صحيحاً $b_1,\ldots,b_n$، تمثّل التسلسل $B$.
يحتوي السطر الرابع على $n$ عدداً صحيحاً موجباً $c_1,\ldots,c_n$، تمثّل التسلسل $C$.
الإخراج
تُكتب النتائج في الملف sequence.out.
لكل مجموعة بيانات، أخرج سطراً واحداً فقط يحتوي على عددين صحيحين، يمثّلان على الترتيب $\max_{D\in T(A)}f(D)$ و$\sum_{D\in T(A)}g(D)$ بترديد $1\,000\,000\,007$. انتبه: لا تُؤخذ قيمة $\max_{D\in T(A)}f(D)$ بترديد $1\,000\,000\,007$.
تتضمن المسألة سؤالين فرعيين، ويمكن الحصول على درجة جزئية بالإجابة الصحيحة عن أي منهما. انظر قسم «المهام الفرعية» لمعرفة قواعد التقييم بالتفصيل.
أمثلة
الإدخال 1
0 3 3 5 6 6 3 6 9 1 2 3 6 1 1 4 5 1 4 -1 1 -1 1 -2 2 1 1 1 1 1 1 8 4 2 4 2 2 2 4 4 -2 4 9 -3 4 8 7 8 1 1 1 1 1 1 1 1
الإخراج 1
15 10 1 18 37 48
ملاحظة
يحتوي هذا المثال على ثلاث مجموعات بيانات اختبار.
للمجموعة الأولى، يمكن الحصول على التسلسلات الأربعة التالية:
$D=[5,6,6]$، و$f(D)=0$، و$g(D)=1$؛
$D=[0,1,6]$، و$f(D)=3$، و$g(D)=1$؛
$D=[5,0,0]$، و$f(D)=6+9=15$، و$g(D)=2\times3=6$؛
$D=[0,0,5]$، و$f(D)=3+6=9$، و$g(D)=1\times2=2$.
لذلك، $\max_{D\in T(A)}f(D)=\max\{0,3,15,9\}=15$، و$\sum_{D\in T(A)}g(D)=1+1+6+2=10$.
أمثلة 2
انظر الملفين sequence/sequence2.in وsequence/sequence2.ans في مجلد المتسابق.
يحقق هذا المثال قيود حالتي الاختبار $3,4$.
أمثلة 3
انظر الملفين sequence/sequence3.in وsequence/sequence3.ans في مجلد المتسابق.
يحقق هذا المثال قيود حالتي الاختبار $5,6$.
أمثلة 4
انظر الملفين sequence/sequence4.in وsequence/sequence4.ans في مجلد المتسابق.
يحقق هذا المثال قيود حالة الاختبار $7$.
أمثلة 5
انظر الملفين sequence/sequence5.in وsequence/sequence5.ans في مجلد المتسابق.
يحقق هذا المثال قيود حالتي الاختبار $11,12$.
أمثلة 6
انظر الملفين sequence/sequence6.in وsequence/sequence6.ans في مجلد المتسابق.
يحقق هذا المثال قيود حالات الاختبار من $16$ إلى $18$.
القيود
لتكن $N$ مجموع قيم $n$ لجميع مجموعات البيانات في حالة اختبار واحدة. لجميع بيانات الاختبار، نضمن ما يلي:
$1\leq t\leq20$؛
$1\leq n\leq5000$، و$N\leq4\times10^4$؛
لكل $1\leq i\leq n$، $1\leq A_i\leq10^9$؛
لكل $1\leq i\leq n$، $-10^9\leq B_i\leq10^9$؛
لكل $1\leq i\leq n$، $1\leq C_i\leq10^9$.
| رقم حالة الاختبار | $n\leq$ | $N\leq$ | الخاصية الخاصة |
|---|---|---|---|
| $1,2$ | $8$ | $10^2$ | لا توجد |
| $3,4$ | $200$ | $400$ | B |
| $5,6$ | $200$ | $400$ | لا توجد |
| $7$ | $500$ | $10^3$ | A |
| $8\sim10$ | $500$ | $10^3$ | B |
| $11,12$ | $500$ | $10^3$ | لا توجد |
| $13$ | $3500$ | $3\times10^4$ | A |
| $14,15$ | $3500$ | $3\times10^4$ | B |
| $16\sim18$ | $3500$ | $3\times10^4$ | لا توجد |
| $19,20$ | $5000$ | $4\times10^4$ | لا توجد |
الخاصية الخاصة A: نضمن أن $A_1=A_2=\cdots=A_n=1$.
الخاصية الخاصة B: نضمن أن كل $A_i$، حيث $1\leq i\leq n$، مولّد عشوائياً بشكل مستقل ومنتظم من المجال $[1,10^9]$.
المهام الفرعية
لكل حالة اختبار:
الإجابة الصحيحة عن $\max_{D\in T(A)}f(D)$ لجميع مجموعات البيانات تمنحك $40\%$ من درجة الحالة؛
الإجابة الصحيحة عن $\sum_{D\in T(A)}g(D)$ بترديد $1\,000\,000\,007$ لجميع مجموعات البيانات تمنحك $60\%$ من درجة الحالة.
انتبه: حتى إذا أجبت عن سؤال واحد فقط، يجب أن تخرج عددين صحيحين وفق تنسيق الإخراج، يمثّلان إجابتي السؤالين على الترتيب.