99002024-03-18 14:36:2042Szitakötő (50 pont)python3Futási hiba 38/50316ms133056 KiB
# O(NlogN)

from sys import stdin, stdout
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)
    #DP[N-1]=sufDP[N-1]=2
    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]
        else:
            DP[k]=sufDP[k+1]-sufDP[d[k]]
            #print('xx',k,d[k],sufDP[d[k]],sufDP[k+1],sufDP)
            sufDP[k]=sufDP[k+1]+DP[k]
        #print('DP',DP)
        #print('sufDP',sufDP)
    #print(preW,W,i,N,K,d,pow(2,i+1,mod))
    #print(N,K,d)
    #print(W)
    #print(preW)
    #print(DP)
    #print(sufDP)
    #print(pow(2,i+1,mod),DP[K])
    print((pow(2,i+1,mod)*DP[K-1])%mod)
    
solv()
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/50
1Elfogadva0/018ms11680 KiB
2Futási hiba0/0266ms133056 KiB
3Elfogadva1/118ms12020 KiB
4Elfogadva1/118ms12440 KiB
5Elfogadva1/118ms12320 KiB
6Elfogadva1/117ms12756 KiB
7Elfogadva1/117ms12884 KiB
8Elfogadva1/118ms13152 KiB
9Elfogadva1/118ms13484 KiB
10Elfogadva2/217ms13712 KiB
11Elfogadva2/217ms13948 KiB
12Elfogadva2/218ms13828 KiB
13Elfogadva2/219ms14380 KiB
14Elfogadva2/218ms14360 KiB
15Elfogadva2/219ms14716 KiB
16Elfogadva2/219ms14220 KiB
17Elfogadva2/219ms14524 KiB
18Elfogadva2/219ms14828 KiB
19Elfogadva2/220ms14872 KiB
20Elfogadva2/219ms14592 KiB
21Elfogadva1/117ms14432 KiB
22Futási hiba0/2245ms130640 KiB
23Futási hiba0/2248ms130624 KiB
24Futási hiba0/2264ms130624 KiB
25Elfogadva2/2219ms109060 KiB
26Elfogadva2/283ms36296 KiB
27Futási hiba0/2298ms130484 KiB
28Futási hiba0/2248ms130464 KiB
29Elfogadva2/2180ms55884 KiB
30Futási hiba0/2316ms130256 KiB
31Elfogadva2/285ms36772 KiB