No.2500 Products in a Range
タグ : / 解いたユーザー数 60
作問者 :
suisen
/ テスター :
emthrm
torisasami4
rniya
Problem Statement
You are given an integer sequence $A=(A _ 1, A _ 2, \ldots, A _ n)$ of length $n$ and integers $l, r$.
A not necessarily contiguous subsequence $B$ of $A$ is called a good subsequence if it satisfies the following condition.
- Let $|B|$ denote the length of $B$. For any integers $i, j$ satisfying $1\leq i\lt j\leq |B|$, $l \leq B _ i B _ j\leq r$ holds.
In particular, note that a subsequence of length $1$ is always a good subsequence.
Find the maximum length of a good subsequence.
Input
The input is given from standard input in the following format.
$n\ l\ r$ $A _ 1\ A _ 2\ \cdots A _ n$
- All input values are integers.
- $1\leq n\leq 5000$
- $-10 ^ 9 \leq l\leq r\leq 10 ^ 9$
- $-10 ^ 9 \leq A _ i\leq 10 ^ 9$
Output
Print the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
5 -3 6 1 4 -5 3 2
Output
3
This input represents $n=5,\ l=-3,\ r=6,\ A=(1,4,-5,3,2)$.
For example, $B=(1,-5)$ is a subsequence of $A$, but since $B _ 1 \times B _ 2 = -5 \lt -3 = l$, $B$ is not a good subsequence.
On the other hand, $B=(1,3,2)$ is a subsequence of $A$, and it is a good subsequence because the following $3$ statements hold.
- $l\leq B _ 1\times B _ 2 = 3 \leq r$
- $l\leq B _ 1\times B _ 3 = 2 \leq r$
- $l\leq B _ 2\times B _ 3 = 6 \leq r$
It can be proved that no good subsequence of length $4$ or more exists, so the answer for this input is $3$.
Sample 2
Input
15 48 72 3 -1 4 -1 5 -9 2 -6 5 -3 5 -8 9 -7 9
Output
3
$B=(-9,-6,-8)$ is one of the longest good subsequences.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。