#P17664. [JAG 2026 Summer Camp #2] Vibe Coding

[JAG 2026 Summer Camp #2] Vibe Coding

题目描述

Shobon 决定使用生成式 AI 来帮助开发一个软件项目。该项目包含 NN 个任务。每个任务 ii(i=1,2,…,Ni=1,2,\ldots,N)都有预先确定的实现工作量 AiA_i 和复杂度 BiB_i。

Shobon 可以按任意顺序完成这些任务,但不能同时处理多个任务。

每个任务 ii(i=1,2,…,Ni=1,2,\ldots,N)都可以用以下两种方式之一完成:

  • 手动实现。 Shobon 自己编写代码,需要 AiA_i 单位时间。
  • 使用生成式 AI。 为了让 AI 生成正确的代码,Shobon 需要向 AI 解释当前任务以及此前所有已完成的任务。令 SS 为此前所有已完成任务的复杂度之和。准备这段说明需要 S+BiS+B_i 单位时间。之后 AI 会瞬间完成实现,不需要额外的实现时间。因此,使用 AI 完成这个任务总共需要 S+BiS+B_i 单位时间。

无论使用哪种方式,只要任务 ii 已经完成,它的复杂度 BiB_i 就会计入此后使用生成式 AI 时的 SS。

求完成所有任务所需的最少总时间。

输入格式

输入包含三行,格式如下。

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

第一行给出任务数 NN(1≤N≤2×1051\le N\le 2\times 10^5)。第二行包含 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N,每个整数都在 11 到 10910^9 之间(含端点),表示这 NN 个任务的实现工作量。第三行包含 NN 个整数 B1,B2,…,BNB_1,B_2,\ldots,B_N,每个整数都在 11 到 10810^8 之间(含端点),表示这 NN 个任务的复杂度。

输出格式

在一行中输出完成所有任务所需的最少总时间。

输入输出样例 #1

输入 #1

3
10 6 10
5 2 4

输出 #1

18

输入输出样例 #2

输入 #2

1
4
10

输出 #2

4

输入输出样例 #3

输入 #3

5
100 100 100 100 100
5 1 4 2 3

输出 #3

35

输入输出样例 #4

输入 #4

12
18 7 25 12 30 5 16 22 9 28 14 20
6 11 2 8 1 13 5 3 10 4 9 7

输出 #4

118

说明/提示

对于样例输入 1,可以依次使用生成式 AI 完成任务 22 和 33,然后手动实现任务 11。

  • 开始任务 22 时,还没有完成任何任务。这个任务需要 0+B2=20+B_2=2 单位时间。
  • 开始任务 33 时,任务 22 已经完成。这个任务需要 B2+B3=2+4=6B_2+B_3=2+4=6 单位时间。
  • 最后,手动实现任务 11 需要 A1=10A_1=10 单位时间。

因此,可以用 2+6+10=182+6+10=18 单位时间完成全部任务,这就是最少时间。