Submission #7080333

---

Source Code Expand

def mul(S, l, r):
    p = 1
    for i in range(l, r):
        p *= S[i]
    return p

def solve0(N, K, S):

    answer = 0
    ml, mr = 0, 0
    for l in range(N):
        for r in range(l, N+1):
            if mul(S, l, r) <= K:
                if answer < r-l:
                    answer = r-l
                    ml, mr = l, r
    #print(S[ml:mr], mul(S, ml, mr), K)
    return answer

def solve(N, K, S):
    answer = 0
    ml, mr = 0, 0
    l = 0
    r = 0
    while l < N:
        if l == r:
            p = 1
        # [l, r)
        #print("start", (l, r), "P=%d"%p)
        while r < N and p * S[r] <= K:
            p *= S[r]
            r += 1
            #print("     ", (l, r), p)
        if p <= K and answer < r - l:
            #print(S[l:r], "P=%d"%p, (l, r), r- l)
            ml, mr = l, r
            answer = r - l
        if l < r:
            p = p // S[l]
        l += 1
        if r < l:
            r = l
    #print(S[ml:mr], mul(S, ml, mr), K)
    return answer

def test():
    from random import randint
    N = 10
    K = 300000
    for i in range(10000):
        S = [randint(1, 10) for i in range(N)]
        s0 = solve0(N, K, S)
        s = solve(N, K, S)
        if s0 != s:
            with open("8", "w") as f:
                print(N, K, file=f)
                for a in S:
                    print(a, file=f)
            print("NG")
            return
    print("ok", i)

#test()

N, K = map(int, input().split())
S = [0]*N
for i in range(N):
    S[i] = int(input())
if min(*S) == 0:
    print(len(S))
else:
    s = solve(N, K, S)
    print(s)

Submission Info

Judge Result