#G1165. [GESP202603 六级] 选数

[GESP202603 六级] 选数

[GESP202603 六级] 选数

题目描述

给定两个包含 nn 个整数的数组 a=[a1,…,an]a=[a_1, \dots, a_n] 与 b=[b1,…,bn]b=[b_1, \dots, b_n]。你需要指定若干下标 p1<p2<⋯<pkp_1 < p_2 < \cdots < p_k(1≤k≤n1 \le k \le n)使得以下条件成立:

  • 1≤pi≤n1 \le p_i \le n(1≤i≤k1 \le i \le k);
  • pi+1≥pi+bpip_{i+1} \ge p_i + b_{p_i}(1≤i<k1 \le i < k)。

你需要在满足以上条件的前提下最大化 ∑i=1kapi\sum_{i=1}^{k} a_{p_i},也即最大化数组 aa 对应下标的整数之和。

输入格式

  • 第一行,一个正整数 nn,表示数组长度。
  • 第二行,nn 个非负整数 a1,a2,…,ana_1, a_2, \dots, a_n,表示数组 aa。
  • 第三行,nn 个非负整数 b1,b2,…,bnb_1, b_2, \dots, b_n,表示数组 bb。

输出格式

一行,一个整数,表示在满足下标条件的前提下,数组 aa 对应下标的整数之和的最大值。

样例 #1

样例输入 #1

4
1 2 3 4
3 3 1 1

样例输出 #1

7

样例 #2

样例输入 #2

6
1 1 4 5 1 4
1 2 3 2 1 0

样例输出 #2

11

数据范围

测试点 数据范围 说明
1~4 2≤n≤1032 \le n \le 10^3 无
全部 2≤n≤1052 \le n \le 10^5,0≤ai≤1090 \le a_i \le 10^9,0≤bi≤n0 \le b_i \le n

时间限制与内存限制

  • 时间限制:1.0 s
  • 内存限制:512.0 MB