No.2500 Products in a Range
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 59
作問者 :
suisen
/ テスター :
👑 
emthrm
torisasami4
rniya
タグ : / 解いたユーザー数 59
作問者 :
suisen
/ テスター :
👑 emthrm
torisasami4
rniya
問題文最終更新日: 2023-09-03 00:29:39
問題文
長さ $n$ の整数列 $A=(A _ 1, A _ 2, \ldots, A _ n)$ および整数 $l, r$ が与えられます。
$A$ の 連続とは限らない 部分列 $B$ であって、次の条件を満たすものを よい部分列 と呼びます。
- $B$ の長さを $|B|$ と表す。$1\leq i\lt j\leq |B|$ を満たす任意の整数 $i, j$ に対して、$l \leq B _ i B _ j\leq r$ が成り立つ。
特に、長さ $1$ の部分列は必ず よい部分列 であることに注意してください。
よい部分列 の長さの最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられます。
$n\ l\ r$ $A _ 1\ A _ 2\ \cdots A _ n$
- 入力は全て整数で与えられる。
- $1\leq n\leq 5000$
- $-10 ^ 9 \leq l\leq r\leq 10 ^ 9$
- $-10 ^ 9 \leq A _ i\leq 10 ^ 9$
出力
答えを $1$ 行に出力し、改行してください。
サンプル
サンプル1
入力
5 -3 6 1 4 -5 3 2
出力
3
この入力は $n=5,\ l=-3,\ r=6,\ A=(1,4,-5,3,2)$ を表します。
例えば $B=(1,-5)$ は $A$ の部分列ですが、$B _ 1 \times B _ 2 = -5 \lt -3 = l$ より $B$ は よい部分列 ではありません。
一方 $B=(1,3,2)$ は $A$ の部分列であり、次の $3$ つが成り立つので よい部分列 です。
- $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$
長さ $4$ 以上の よい部分列 は存在しないことを証明できるので、この入力に対する答えは $3$ となります。
サンプル2
入力
15 48 72 3 -1 4 -1 5 -9 2 -6 5 -3 5 -8 9 -7 9
出力
3
$B=(-9,-6,-8)$ は最長の よい部分列 のうちの一つです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。