33OJ
登录 注册

#P17503. [ICPC 2026 Wuhan I] Deletion Game

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

[ICPC 2026 Wuhan I] Deletion Game

题目描述

八千代有一个长度为 nn 的整数序列 SS,序列的每个位置(下标从 11 开始)都有一个权值 aia_i。

她可以将这个序列连同权值一起复制并首尾拼接若干次。具体来说,若他选择拼接使得总份数为 mm(m≥1m \ge 1),则会得到一个长度为 m×nm\times n 的新序列 S′S' 和对应的新权值序列 a′a'。对于任意的 0≤c<m0 \le c<m 和 1≤i≤n1 \le i \le n,满足 Scn+i′=SiS'_{cn+i}=S_i 且 acn+i′=aia'_{cn+i}=a_i。

八千代现在想对得到的新序列 S′S' 进行若干次(可以为 00 次)消除操作。每次操作的规则如下:

  • 选定两个下标 i,ji,j 满足 1≤i<j≤∣S′∣1 \le i<j \le |S'|,且 Si′=Sj′S'_i=S'_j。
  • 将 S′S' 和 a′a' 中的第 (i+1)(i+1) 个到第 jj 个元素删去。
  • 操作完成后,序列剩余的元素会按照原顺序重新紧凑排列,序列的总长度相应减少。

八千代想知道,在经过恰当份数的拼接和任意次消除操作后,整个剩余序列的权值和最小是多少?以及在保证权值和最小的前提下,最少需要多少份原序列拼接(即求最小的 mm)?

输入格式

输入包含三行。

第一行包含一个整数 nn(1≤n≤3×1051 \le n \le 3\times10^5),表示初始序列 SS 的长度。

第二行包含 nn 个整数 S1,S2,⋯ ,SnS_1,S_2,\cdots,S_n(1≤Si≤3×1051 \le S_i \le 3\times10^5),表示初始序列 SS 的元素。

第三行包含 nn 个整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n(1≤ai≤3×1051 \le a_i \le 3\times10^5),表示每个位置对应的权值。

输出格式

输出一行包含两个整数,用空格隔开:

  • 第一个整数表示经过操作后,剩余序列的最小权值和。
  • 第二个整数表示为了达到该最小权值和,最少需要的原序列总份数。
6
1 1 4 5 1 4
1 9 1 9 8 10
2 1

提示

在本样例中,最优策略是仅使用 11 份原序列(即 m=1m=1,不进行额外复制)。

初始序列 S′S' 为 [1,1,4,5,1,4][1,1,4,5,1,4],对应的权值 a′a' 为 [1,9,1,9,8,10][1,9,1,9,8,10]。

八千代可以进行以下两次操作:

  1. 选择 i=1,j=2i=1,j=2(此时 S1′=S2′=1S'_1=S'_2=1),删去第 i+1∼ji+1\sim j 个元素(即删去第 22 个元素)。操作后序列 S′S' 变为 [1,4,5,1,4][1,4,5,1,4],权值 a′a' 变为 [1,1,9,8,10][1,1,9,8,10]。
  2. 在新序列中选择 i=2,j=5i=2,j=5(此时 S2′=S5′=4S'_2=S'_5=4),删去第 i+1∼ji+1\sim j 个元素(即删去第 3,4,53,4,5 个元素)。操作后序列 S′S' 剩余 [1,4][1,4],权值 a′a' 剩余 [1,1][1,1]。

此时无法继续消除,剩余序列的权值和为 1+1=21+1=2。可以证明在任何拼接份数和操作下,权值和不可能小于 22。