#P12512. 「OOI 2024 Day 2」三个数组

    ID: 11675 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000贪心排序数据结构前缀和动态规划

「OOI 2024 Day 2」三个数组

题目描述

给定三个长度为 nn 的数组 DD、LL 和 RR,元素编号从 11 开始,以及两个数字 a0a_{0} 和 b0b_{0}。你需要按照以下规则构建两个长度为 n+1n+1 的数组 AA 和 BB:

  1. A0=a0A_{0} = a_{0},B0=b0B_{0} = b_{0}。
  2. 对于从 11 到 nn 的每个 ii,执行以下操作:
    • 初始设置 Ai=Ai−1+DiA_{i} = A_{i-1} + D_{i} 和 Bi=Bi−1+DiB_{i} = B_{i-1} + D_{i}。
    • 选择恰好一种以下操作并应用:
      • Ai=min⁡(Ai,Li)A_{i} = \min(A_{i}, L_{i})
      • Bi=min⁡(Bi,Ri)B_{i} = \min(B_{i}, R_{i})

你的目标是构建数组 AA 和 BB,以最大化 An+BnA_{n} + B_{n} 的值。找出通过上述操作可以获得的最大 An+BnA_{n} + B_{n} 值。

输入格式

第一行包含一个整数 nn (1≤n≤100000)(1 \leq n \leq 100000),表示数组 DD、LL 和 RR 的长度。

第二行包含 nn 个整数 D1,D2,…,DnD_{1}, D_{2}, \ldots, D_{n} (0≤Di≤109)(0 \leq D_{i} \leq 10^{9}),表示数组 DD。

第三行包含 nn 个整数 L1,L2,…,LnL_{1}, L_{2}, \ldots, L_{n} (0≤Li≤109)(0 \leq L_{i} \leq 10^{9}),表示数组 LL。

第四行包含 nn 个整数 R1,R2,…,RnR_{1}, R_{2}, \ldots, R_{n} (0≤Ri≤109)(0 \leq R_{i} \leq 10^{9}),表示数组 RR。

第五行包含两个整数 a0a_{0} 和 b0b_{0} (0≤a0,b0≤109)(0 \leq a_{0}, b_{0} \leq 10^{9})。

输出格式

输出一个整数,即通过构建数组 AA 和 BB 可以获得的最大 An+BnA_{n} + B_{n} 值。

5
4 0 7 0 8
10 5 3 7 7
8 5 9 2 23
4 8

34

数据范围与提示

详细子任务附加限制及分值如下表所示:

子任务 分值 附加限制 子任务依赖 备注
11 1313 n≤15n \leq 15 00
22 1818 n≤300n \leq 300 0,10, 1
33 1414 n≤5000n \leq 5000,Di=0D_{i} = 0
44 1616 n≤5000n \leq 5000 0∼30 \sim 3
55 1919 Di=0D_{i} = 0 33
66 2020 0∼50 \sim 5