กำหนดลำดับจำนวนเต็มสองลำดับที่มีความยาว $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$ เขาสามารถแก้ไขลำดับ $A$ ได้ดังนี้:
- เลือกดัชนีสองตำแหน่งที่ อยู่ติดกัน $i,j$ ในลำดับ $A$ (กล่าวคือ $1\le i,j\le n$ และ $|i-j|=1$) หาก $a_i\le a_j$ ให้เปลี่ยน $a_j$ เป็น $a_j-a_i$ และเปลี่ยน $a_i$ เป็น $0$ พร้อมกัน
小 L สามารถแก้ไขกี่ครั้งก็ได้ หรือไม่แก้ไขเลยก็ได้ สำหรับลำดับ $D$ ทั้งหมดที่ได้จากการแก้ไขลำดับ $A$ ด้วยวิธีข้างต้น 小 L ต้องการหาค่าสูงสุดของ $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
หมายเหตุ
ตัวอย่างนี้มีข้อมูลทดสอบทั้งหมดสามชุด
สำหรับชุดข้อมูลแรก สามารถได้ลำดับ 4 ลำดับต่อไปนี้:
- $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\sim18$
ข้อจำกัด
ให้ $N$ เป็นผลรวมของ $n$ ของข้อมูลทดสอบทุกชุดภายในกรณีทดสอบเดียว สำหรับข้อมูลทดสอบทั้งหมด รับประกันว่า:
- $1\le t\le20$
- $1\le n\le5000$, $N\le4\times10^4$
- สำหรับทุก $1\le i\le n$ มี $1\le A_i\le10^9$
- สำหรับทุก $1\le i\le n$ มี $-10^9\le B_i\le10^9$
- สำหรับทุก $1\le i\le n$ มี $1\le C_i\le10^9$
| หมายเลขกรณีทดสอบ | $n\le$ | $N\le$ | คุณสมบัติพิเศษ |
|---|---|---|---|
| $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: รับประกันว่าสำหรับทุก $1\le i\le n$ ค่า $A_i$ ถูกสุ่ม อย่างอิสระและสม่ำเสมอ จากช่วง $[1,10^9]$
งานย่อย
สำหรับแต่ละกรณีทดสอบ:
- หากตอบ $\max_{D\in T(A)}f(D)$ ของข้อมูลทดสอบทุกชุดถูกต้อง จะได้ $40\%$ ของคะแนนกรณีทดสอบนั้น
- หากตอบ $\sum_{D\in T(A)}g(D)$ เมื่อหารเอาเศษด้วย $1{,}000{,}000{,}007$ ของข้อมูลทดสอบทุกชุดถูกต้อง จะได้ $60\%$ ของคะแนนกรณีทดสอบนั้น
โปรดทราบว่า แม้ผู้เข้าแข่งขันจะตอบเพียงข้อเดียว ก็ยังต้องส่งออกจำนวนเต็มสองจำนวนตามรูปแบบข้อมูลส่งออก โดยแต่ละจำนวนตรงกับคำตอบของแต่ละข้อ