← 返回题目列表

Codeforces · 1940/B

B. 三个阵列

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

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

Three Arrays - 原题 PDF 第 1 页
原题PDF第5页
Three Arrays - 原题 PDF 第 2 页
原题PDF第6页
可复制的 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