← 返回题目列表

AtCoder · joig2026final_c

C. 装饰蛋糕(蛋糕4)

中文机器翻译题面 查看原题

配点 : 100 点

問題文

JOI君和IOI酱是兄妹,今天是IOI酱的生日。 JOI君为IOI酱庆祝生日 我购买了 N 蛋糕。为了蛋糕 蛋糕编号为 1 假设一直下雨,直到 N 。 i (1 \leqq i \leqq N) 的大小是 A_i 。 JOI君想要取悦IOI酱, 我制定了N 计划。i 番目 (1 \leqq i \leqq N) 计划很简单 i 甜蜜 V_i 草莓 1 是装饰个人。

JOI君对蛋糕的外观很讲究,所以我们确保满足以下所有条件。 选择并执行至少 0 计划。

  • 用草莓装饰不同 2 对于两个蛋糕,它们的大小之和为 这不是 S 。
  • 用草莓装饰不同 2 对于两个蛋糕,它们之间的大小差异为 D 。

要执行的计划数量为 1 请注意,当小于或等于 1 时,始终满足条件。

由于IOI喜欢甜的东西,我们希望尽可能增加装饰草莓的总甜度。在这里,1 如果不装饰草莓,则装饰草莓的总甜度为 0 。

给定有关蛋糕和草莓的信息,编写一个程序,找出装饰草莓的最大可能甜度总和。


入力

输入是按以下格式从标准输入给出的。

N S D
A_1 A_2 \cdots A_N
V_1 V_2 \cdots V_N

出力

装饰草莓的最大可能甜度总和被写入标准输出。 1 行。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq S \leqq 10^9.
  • 1 \leqq D \leqq 10^9.
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq V_i \leqq 10^9 (1 \leqq i \leqq N).
  • 所有输入值均为整数。

小課題

  1. (7 点) N \leqq 20.
  2. (14 点) S \leqq 40,D \leqq 20,A_i \leqq 20 (1 \leqq i \leqq N).
  3. (18 点) S = 1.
  4. (30 点) D = 1,S 是奇数。
  5. (15 点) D = 1.
  6. (16 点)没有额外的限制。 考虑选择

入力例 1

5 8 3
3 4 5 6 7
10 6 7 5 4

出力例 1

18

計画 2,3,4 并执行它。 用草莓装饰的蛋糕 与 2,3,4 有何不同 2 即使您选择其中一个,尺寸之和也是 8 区别在于 3 永远不会发生。 因此,这些计划是可行的。 这里,装饰草莓的总甜度是 6 + 7 + 5 = 18 变为。

总甜度为 18 由于无法选择大于18 。

此输入示例是一个小作业。 1,2,6 满足约束。


入力例 2

3 1 3
4 7 10
3 10 8

出力例 2

11

此输入示例是一个小作业。 1,2,3,6 满足约束。


入力例 3

10 1 1
1 2 3 4 5 6 7 8 9 10
3 1 4 1 5 9 2 6 5 3

出力例 3

25

此输入示例满足所有子任务约束。