以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Problem B. Three Arrays
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 megabytes
You are given three arrays D, L, and R of length n, with elements indexed from 1, as well as the integers
a0 and b0. You construct two arrays A and B of length n + 1 according to the following rules:
1. A0 = a0, B0 = b0
2. For all i from 1 to n, perform the following actions:
(a) Set the elements as Ai = Ai−1 + Di and Bi = Bi−1 + Di.
(b) Choose exactly one of the following operations and apply it:
• Ai = min(Ai, Li)
• Bi = min(Bi, Ri)
You want to construct arrays A and B to maximize the value of An + Bn. Find the maximum value of
An + Bn that can be obtained by performing the described actions.
Input
The first line contains a single integer n (1 ≤n ≤100 000) — the length of arrays D, L, and R.
The second line contains n integers D1, D2, . . . , Dn (0 ≤Di ≤109) — the array D.
The third line contains n integers L1, L2, . . . , Ln (0 ≤Li ≤109) — the array L.
The fourth line contains n integers R1, R2, . . . , Rn (0 ≤Ri ≤109) — the array R.
The fifth line contains two integers a0 and b0 (0 ≤a0, b0 ≤109).
Output
Output a single integer — the maximum possible value of An + Bn among all possible ways to construct
arrays A and B.
Scoring
The tests for this problem consist of six groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed. Please note that passing the example tests is not
required for some groups. Offline-evaluation means that the results of testing your solution on this
group will only be available after the end of the competition.
Additional constraints
Group Points Required groups Comment
n Di
0 0 – – – Examples.
1 13 n ≤15 – 0
2 18 n ≤300 – 0, 1
3 14 n ≤5000 Di = 0 –
4 16 n ≤5000 – 0–3
5 19 – Di = 0 3
6 20 – – 0–5 Offline-evaluation.
Page 5 of 12
XVIII Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules)
Russia, Moscow, March, 9, 2024
Example
standard input standard output
5 34
4 0 7 0 8
10 5 3 7 7
8 5 9 2 23
4 8
Note
In the first set of input data, the following sequence of actions leads to the maximum answer:
1. A0 = 4, B0 = 8.
2. A1 = A0 + D1 = 4 + 4 = 8, B1 = B0 + D1 = 8 + 4 = 12.
3. The minimum is applied to A1 = min(A1, L1) = min(10, 8) = 8, the value of B1 = 12 remains the
same.
4. A2 = A1 + D2 = 8 + 0 = 8, B2 = B1 + D2 = 12 + 0 = 12.
5. The minimum is applied to A2 = min(A2, L2) = min(5, 8) = 5, the value of B2 = 12 remains the
same.
6. A3 = A2 + D3 = 12, B3 = B2 + D3 = 19.
7. The minimum is applied to A3 = min(A3, L3) = 3, the value of B3 = 19 remains the same.
8. A4 = A4 + D3 = 3, B4 = B3 + D4 = 19.
9. The minimum is applied to A4 = min(A4, L4) = 3, the value of B4 = 19 remains the same.
10. A5 = A5 + D4 = 11, B5 = B4 + D5 = 27.
11. The value of A5 = 11 remains the same, B5 = min(B5, R5) = min(27, 23) = 23.
12. A5 + B5 = 11 + 23 = 34.
It can be shown that this is the maximum value.
Page 6 of 12