99022024-03-18 14:53:4042Szitakötő (50 pont)pypy3Runtime error 36/50171ms167700 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
    preW.append(0)
    W[N-1]=preW[N-1]=0
    W[N-2]=preW[N-2]=0
    for k in range(N-2,K-2,-1):
        if k not in d:
            W[k]=pow(2,N-k-1,mod)
            preW[k]=preW[k+1]+W[k]
        else:
            W[k]=preW[k+1]-preW[d[k]]
            preW[k]=preW[k+1]+W[k]
    print((pow(2,i+1,mod)*W[K-1])%mod)
    
solv()
SubtaskSumTestVerdictTimeMemory
base36/50
1Accepted0/057ms87848 KiB
2Runtime error0/0155ms167700 KiB
3Accepted1/148ms88524 KiB
4Accepted1/148ms88696 KiB
5Accepted1/143ms88768 KiB
6Accepted1/148ms89444 KiB
7Accepted1/143ms89768 KiB
8Accepted1/141ms90156 KiB
9Accepted1/146ms89900 KiB
10Accepted2/245ms90412 KiB
11Accepted2/250ms90068 KiB
12Accepted2/248ms90732 KiB
13Accepted2/252ms93828 KiB
14Accepted2/250ms93892 KiB
15Accepted2/252ms94056 KiB
16Accepted2/252ms93952 KiB
17Accepted2/254ms94320 KiB
18Accepted2/254ms94092 KiB
19Accepted2/252ms94256 KiB
20Accepted2/252ms94404 KiB
21Accepted1/148ms94364 KiB
22Runtime error0/2149ms164604 KiB
23Runtime error0/2150ms164368 KiB
24Runtime error0/2171ms164628 KiB
25Runtime error0/2165ms164548 KiB
26Accepted2/276ms117688 KiB
27Runtime error0/2146ms164612 KiB
28Runtime error0/2150ms164016 KiB
29Accepted2/2137ms135968 KiB
30Runtime error0/2158ms164268 KiB
31Accepted2/275ms117048 KiB