Problem:


MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']], skipTags: ["script","noscript","style","textarea","code"]}
});

F： 掛け算は楽しい - Multiplication Is Interesting -

物語

男子高生の難波列くんは、彼女の誕生日に数列をプレゼントしようと考えている。彼女は掛け算が大好きな女の子なので、難波くんは彼女にできるだけ多くの掛け算を楽しんてもらえるような数列をプレゼントしたいと思っている。しかし、計算結果が 2^{20} を超える値になると彼女の機嫌が途端に悪くなってしまう（通常の人類は 2^{20}という膨大な数を計算できないため、これでも彼女は随分と寛大な人であると言える）。彼女の機嫌を損なわないように、できるだけ多くの掛け算を楽しんでもらえる数列を難波くんが作ったので、あなたの仕事はその数列が彼女を十分に楽しませられるか検証するプログラムを作ることである。つまり、あなたの仕事は数列の連続する部分列の中で、部分列の総積が K を超えない最長の部分列の長さを答えるプログラムを作ることである。

問題

長さ N の非負実数列 S = s_1, s_2, ..., s_N と 非負実数 K がある。 あなたの仕事は、以下の条件を満たす S の連続する部分列のうち、次の条件を満たす最長の部分列の長さを求めることである。このとき、部分列の長さは 1 以上でなければならない。

 S の連続する部分列 $T = s_\ell, \ldots, s_r$ について $\prod_{i = \ell, \ldots, r} s_i \leq$ Kを満たす。

もし条件を満たす部分列が一つも存在しないときは、 0 を出力せよ。

入力形式

入力は次の形式で与えられる．

N K
s_1
s_2
$\dots$
s_N

1 行目には数列の長さ N と 部分列の総積の上限 K が与えられる。続く N 行のうち、 i 行目では非負実数列 S の i 番目の実数 s_i が与えられる。

制約

 1 \leq N \leq 100,000 

 0 \leq s_i \leq 2.00 

 0 \leq K \leq 1,048,576

 N は整数、K と s_i は小数点第 3 位以下を含まない実数である

出力形式

S の部分列の総積が K を超えない最長の部分列の長さを 1 行に出力せよ。

入力例1

6 2.01
1.10 
1.44
0.91
2.00
1.12
1.55

出力例1

3

入力例2

8 12.22
2.00
2.00
2.00
1.91
2.00
2.00
2.00
0.01

出力例2

8


Sample input:
6 2.01
1.10
1.44
0.91
2.00
1.12
1.55


Sample output:
3

Submission status: Accepted

Solution code:
from decimal import *
import sys
import copy

def main():
    getcontext().prec = 1000
    input = sys.stdin.readline
    n, k = input().split()
    n = int(n)
    k = Decimal(k)
    a = [Decimal(input()) for i in range(n)]
    if Decimal(0) in a:
        print(n)
        sys.exit()
    if k == Decimal(0):
        print(0)
        sys.exit()
    left = copy.copy(a)
    right = copy.copy(a)
    for i in range(n-1):
        left[i + 1] *= left[i]
    for i in reversed(range(n-1)):
        right[i] *= right[i + 1]
    mul = left[-1]
    right.append(Decimal(1))
    r = []
    for i, x in enumerate(right):
        while r and r[-1][1] <= x:
            r.pop()
        r.append((i, x))
    l = [(-1, Decimal(1))]
    for i, x in enumerate(left):
        if not l or l[-1][1] < x:
            l.append((i, x))
    ans = 0
    at = -1
    for i, x in l:
        while at + 1 < len(r) and x * r[at + 1][1] * k >= mul:
            at += 1
        if at >= 0 and ans < r[at][0] - i - 1:
            ans = r[at][0] - i - 1
    print(ans)
main()