AtCoder Beginner Contest 032

C - 列


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

長さ 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

Submit提出する