#P17503. [ICPC 2026 Wuhan I] Deletion Game
[ICPC 2026 Wuhan I] Deletion Game
Problem Description
Yachiyo has an integer sequence of length , and each position in the sequence (indexed from ) has a weight .
She can copy this sequence together with its weights and concatenate the copies end to end several times. Specifically, if she chooses to concatenate copies in total (), she will obtain a new sequence of length and a corresponding new weight sequence . For any and , we have and .
Now Yachiyo wants to perform several elimination operations on the resulting sequence (possibly zero times). Each operation works as follows:
- Choose two indices such that and .
- Delete the -th through -th elements from both and .
- After the operation, the remaining elements are compacted in their original order, and the total length decreases accordingly.
Yachiyo wants to know: after choosing an appropriate number of copies and performing any number of elimination operations, what is the minimum possible sum of the weights of the remaining sequence? Also, under the condition that this minimum weight sum is achieved, what is the minimum number of copies of the original sequence needed (that is, the minimum )?
Input Format
The input contains three lines.
The first line contains an integer (), the length of the initial sequence .
The second line contains integers (), representing the elements of the initial sequence .
The third line contains integers (), representing the weight of each position.
Output Format
Output one line containing two integers separated by a space:
- The first integer is the minimum possible sum of weights of the remaining sequence after the operations.
- The second integer is the minimum total number of copies of the original sequence needed to achieve that minimum weight sum.
6
1 1 4 5 1 4
1 9 1 9 8 10
2 1
Hint
In this sample, the optimal strategy is to use only copy of the original sequence (that is, , with no extra copying).
The initial sequence is , and the corresponding weight sequence is .
Yachiyo can perform the following two operations:
- Choose (at this time ), and delete the -th through -th elements (that is, delete the 2nd element). After the operation, becomes , and becomes .
- In the new sequence, choose (at this time ), and delete the -th through -th elements (that is, delete the 3rd, 4th, and 5th elements). After the operation, the remaining is , and the remaining is .
At this point, no further elimination is possible, and the sum of the remaining weights is . It can be proved that under any number of copies and any sequence of operations, the weight sum cannot be smaller than .