第 78 场 AtCoder Grand Contest
稳健递增子序列AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$ and non-negative integers $X,Y$.
给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$，以及非负整数 $X,Y$。AI (CI翻译)
Find the maximum length $M$ of a subsequence $B=(B_1,B_2,\ldots,B_M)$ of $A$ that satisfies both of the following conditions.
请找出 $A$ 的一个子序列 $B=(B_1,B_2,\ldots,B_M)$，使其满足以下两个条件，并求 $M$ 的最大值。AI (CI翻译)
$B_i\ge B_{i-1}-X$holds for every integer$i$satisfying$2\le i\le M$.$B_i\ge B_{i-2}-(X+Y)$holds for every integer$i$satisfying$3\le i\le M$.
- 对于所有满足
$2\le i\le M$的整数$i$，都有$B_i\ge B_{i-1}-X$。 - 对于所有满足
$3\le i\le M$的整数$i$，都有$B_i\ge B_{i-2}-(X+Y)$。
Constraints
约束条件
AI (CI翻译)$1\le N\le 5\times 10^5$$1\le A_i\le 10^9$$0\le X,Y\le 10^9$- All input values are integers.
$1\le N\le 5\times 10^5$$1\le A_i\le 10^9$$0\le X,Y\le 10^9$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入通过标准输入给出，格式如下：AI (CI翻译)
N X Y
A_1 A_2 \ldots A_NN X Y
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
7 3 1
8 6 3 7 5 2 6
Output #1
5
The subsequence $(8,6,7,5,6)$ satisfies the conditions. There is no subsequence of length $6$ or greater that satisfies the conditions, so output $5$.
Input #2
5 0 0
5 4 3 2 1
Output #2
1
Input #3
15 441943320 890669835
693547414 783888993 702664735 345257171 73365711 320257375 683236857 951712144 151653382 210806164 439829968 987667432 978973992 565844495 621822141
Output #3
13
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。