C - 列
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
長さ N の非負整数列 S={s_1,s_2,...,s_N} と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないといけません。
- その部分列に含まれる全ての要素の値の積は、K 以下である。
もし条件を満たす部分列が一つも存在しないときは、0 を出力してください。
入力
入力は以下の形式で標準入力から与えられる。
N K s_1 s_2 : s_N
- 1 行目には、数列の長さを表す整数 N (1≦N≦10^5) と問題文中の整数 K (0≦K≦10^9) が空白区切りで与えられる。
- 2 行目からの N 行には、数列の各要素の値が与えられる。そのうち i(1≦i≦N) 行目には、s_i (0≦s_i≦10^9) が書かれている。
部分点
この問題には部分点が設定されている。満点は 100 点である。
- N≦1000 を満たすデータセット 1 に正解した場合は、20 点が与えられる。
- 追加制約のないデータセット 2 に正解した場合、上記の点数に加え 80 点が与えられる。
出力
出力は以下の形式で標準出力に行うこと。
1 行目に、含まれる全ての要素の値の積が K 以下となる連続する部分列のうち最長のものの長さを出力せよ。もし条件を満たす部分列が一つも存在しないときは、0 を出力せよ。末尾の改行を忘れないこと。
入力例1
7 6 4 3 1 1 2 10 2
出力例1
4
部分列 S[2..5]=s_2,s_3,s_4,s_5 を選ぶと、積は 3×1×1×2=6 となり、K 以下になります。
入力例2
6 10 10 10 10 10 0 10
出力例2
6
入力例3
6 9 10 10 10 10 10 10
出力例3
0
入力例4
4 0 1 2 3 4
出力例4
0