99042024-03-18 14:57:4342Szitakötő (50 pont)python3Futási hiba 38/50321ms133204 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=[-1]*N
    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 d[k] == -1:
            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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/50
1Elfogadva0/017ms11648 KiB
2Futási hiba0/0254ms133204 KiB
3Elfogadva1/117ms12076 KiB
4Elfogadva1/117ms12280 KiB
5Elfogadva1/117ms12212 KiB
6Elfogadva1/117ms12528 KiB
7Elfogadva1/118ms12680 KiB
8Elfogadva1/118ms13220 KiB
9Elfogadva1/118ms13100 KiB
10Elfogadva2/218ms13424 KiB
11Elfogadva2/218ms13356 KiB
12Elfogadva2/217ms13644 KiB
13Elfogadva2/220ms13620 KiB
14Elfogadva2/218ms13576 KiB
15Elfogadva2/219ms13988 KiB
16Elfogadva2/219ms13812 KiB
17Elfogadva2/219ms14456 KiB
18Elfogadva2/219ms14848 KiB
19Elfogadva2/219ms14476 KiB
20Elfogadva2/219ms14504 KiB
21Elfogadva1/118ms14436 KiB
22Futási hiba0/2247ms130848 KiB
23Futási hiba0/2252ms130836 KiB
24Futási hiba0/2250ms130780 KiB
25Elfogadva2/2229ms99996 KiB
26Elfogadva2/282ms36456 KiB
27Futási hiba0/2305ms130044 KiB
28Futási hiba0/2250ms130348 KiB
29Elfogadva2/2175ms48528 KiB
30Futási hiba0/2321ms130244 KiB
31Elfogadva2/281ms36680 KiB