#P17820. [Ontak2022]ANT

    ID: 16763 传统题 500~5000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500动态规划数据结构线段树树状数组算法基础模拟

[Ontak2022]ANT

题目描述

给定一个长度为 NN 的序列。第 ii 个元素有数值 aia_i 和权重 wiw_i。

一个非空序列 b0,b1,…,bL−1b_0,b_1,\ldots,b_{L-1} 称为循环交替序列,当且仅当 LL 为偶数,并且将下标对 LL 取模后,每个元素都是严格的局部极大值或严格的局部极小值,二者交替出现。也就是说,相邻元素不能相等,且

$$b_{i-1}<b_i\Longrightarrow b_i>b_{i+1},\qquad b_{i-1}>b_i\Longrightarrow b_i<b_{i+1}.$$

特别地,首尾相邻处也必须满足上述条件。长度为 22 且两元素不同的序列合法。

从原序列中选出一个不必连续的子序列,保持下标递增,使其数值构成循环交替序列,并使所选元素的权重和最大。

输入格式

第一行一个整数 NN。第二行 NN 个整数 a0,…,aN−1a_0,\ldots,a_{N-1}。第三行 NN 个整数 w0,…,wN−1w_0,\ldots,w_{N-1}。

输出格式

输出最大权重和;如果不存在合法的非空子序列,输出 NO。答案可以为负数。

数据范围

1≤N≤500001\le N\le50000,1≤ai≤1091\le a_i\le10^9,−5≤wi≤5-5\le w_i\le5。

子任务

子任务 附加限制 分值
1 N≤20 5
2 N≤500 11
3 N≤10000 27
4 所有 wᵢ=1 17
5 所有 aᵢ≤20 21
6 无额外限制 19

样例 1

输入:

9
6 2 6 3 8 3 10 1 4
1 1 1 1 -1 -1 1 1 1

输出:

6

说明

样例的一种最优子序列为 (6,2,6,3,10,4),权重和为6;只满足线性交替但首尾不闭合的子序列不合法。