33OJ
登录 注册

#P17503. [ICPC 2026 Wuhan I] Deletion Game

    ID: 20231 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Deletion Game

Problem Description

Yachiyo has an integer sequence SS of length nn, and each position in the sequence (indexed from 11) has a weight aia_i.

She can copy this sequence together with its weights and concatenate the copies end to end several times. Specifically, if she chooses to concatenate mm copies in total (m≥1m \ge 1), she will obtain a new sequence S′S' of length m×nm\times n and a corresponding new weight sequence a′a'. For any 0≤c<m0 \le c<m and 1≤i≤n1 \le i \le n, we have Scn+i′=SiS'_{cn+i}=S_i and acn+i′=aia'_{cn+i}=a_i.

Now Yachiyo wants to perform several elimination operations on the resulting sequence S′S' (possibly zero times). Each operation works as follows:

  • Choose two indices i,ji,j such that 1≤i<j≤∣S′∣1 \le i<j \le |S'| and Si′=Sj′S'_i=S'_j.
  • Delete the (i+1)(i+1)-th through jj-th elements from both S′S' and a′a'.
  • 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 mm)?

Input Format

The input contains three lines.

The first line contains an integer nn (1≤n≤3×1051 \le n \le 3\times10^5), the length of the initial sequence SS.

The second line contains nn integers S1,S2,⋯ ,SnS_1,S_2,\cdots,S_n (1≤Si≤3×1051 \le S_i \le 3\times10^5), representing the elements of the initial sequence SS.

The third line contains nn integers a1,a2,⋯ ,ana_1,a_2,\cdots,a_n (1≤ai≤3×1051 \le a_i \le 3\times10^5), 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 11 copy of the original sequence (that is, m=1m=1, with no extra copying).

The initial sequence S′S' is [1,1,4,5,1,4][1,1,4,5,1,4], and the corresponding weight sequence a′a' is [1,9,1,9,8,10][1,9,1,9,8,10].

Yachiyo can perform the following two operations:

  1. Choose i=1,j=2i=1,j=2 (at this time S1′=S2′=1S'_1=S'_2=1), and delete the (i+1)(i+1)-th through jj-th elements (that is, delete the 2nd element). After the operation, S′S' becomes [1,4,5,1,4][1,4,5,1,4], and a′a' becomes [1,1,9,8,10][1,1,9,8,10].
  2. In the new sequence, choose i=2,j=5i=2,j=5 (at this time S2′=S5′=4S'_2=S'_5=4), and delete the (i+1)(i+1)-th through jj-th elements (that is, delete the 3rd, 4th, and 5th elements). After the operation, the remaining S′S' is [1,4][1,4], and the remaining a′a' is [1,1][1,1].

At this point, no further elimination is possible, and the sum of the remaining weights is 1+1=21+1=2. It can be proved that under any number of copies and any sequence of operations, the weight sum cannot be smaller than 22.