99062024-03-18 15:01:5042Szitakötő (50 pont)python3Accepted 50/50303ms61212 KiB
# O(N)

from sys import stdin
input=stdin.readline

mod=10**9+7

def solv():
    N,K = [int(x) for x in input().split()]
    W = [int(x) for x in input().split()]
    if N==1:
        print(2)
        return
    if K==1:
        print(0)
        return
    preW=[0]*N
    for i in range(N):
        preW[i]=preW[i-1]+W[i]
    i=K-2
    while preW[i]*2 > preW[K-1]:
        i-=1
    # 2^(i+1) lehetoseg balra
    if K==N:
        print(pow(2,i+2,mod))
        return
    # K<N:
    d={}
    j=K
    while j<N and 2*preW[K-1] > preW[j]:
        j+=1
    if j==N:
        print(pow(2,i+1+N-K,mod))
        return
    if K==j:
        print(0)
        return
    d={K-1:j}
    for k in range(K,N):
        while j<N and 2*preW[k] > preW[j]:
            j+=1
        if j==N:
            break
        if k+1==j:
            print(0)
            return
        d[k]=j
    DP=[0]*N
    sufDP=[0]*(N+1)
    for k in range(N-2,K-2,-1):
        if k not in d:
            DP[k]=pow(2,N-k-1,mod)
            sufDP[k]=(sufDP[k+1]+DP[k])%mod
        else:
            DP[k]=(sufDP[k+1]-sufDP[d[k]])%mod
            sufDP[k]=(sufDP[k+1]+DP[k])%mod
    print((pow(2,i+1,mod)*DP[K-1])%mod)
    
solv()
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/018ms11544 KiB
2Accepted0/0261ms58604 KiB
3Accepted1/118ms12128 KiB
4Accepted1/117ms11852 KiB
5Accepted1/118ms12304 KiB
6Accepted1/117ms12596 KiB
7Accepted1/118ms12652 KiB
8Accepted1/118ms12928 KiB
9Accepted1/118ms13180 KiB
10Accepted2/217ms13524 KiB
11Accepted2/217ms13700 KiB
12Accepted2/218ms13740 KiB
13Accepted2/219ms14220 KiB
14Accepted2/218ms14176 KiB
15Accepted2/219ms14316 KiB
16Accepted2/218ms14028 KiB
17Accepted2/219ms14404 KiB
18Accepted2/219ms14352 KiB
19Accepted2/219ms14680 KiB
20Accepted2/219ms14388 KiB
21Accepted1/118ms14220 KiB
22Accepted2/2252ms60912 KiB
23Accepted2/2230ms55640 KiB
24Accepted2/2266ms60304 KiB
25Accepted2/2190ms45776 KiB
26Accepted2/282ms35956 KiB
27Accepted2/2289ms50748 KiB
28Accepted2/2264ms61212 KiB
29Accepted2/2180ms41532 KiB
30Accepted2/2303ms60044 KiB
31Accepted2/279ms36284 KiB