Problem: There are N candles placed on a number line. The i-th candle from the left is placed on coordinate x_i. Here, x_1 < x_2 < ... < x_N holds.  Initially, no candles are burning. Snuke decides to light K of the N candles.  Now, he is at coordinate 0. He can move left and right along the line with speed 1. He can also light a candle when he is at the same position as the candle, in negligible time.  Find the minimum time required to light K candles.

Submission attempts (in order):
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

#WAA TLEEEEEEEEEE
n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]

ll=len(l)
rr=len(r)

ans=sum(l)*2+sum(r)*2
if ll==k: ans=min(ans,sum(l))
if rr==k: ans=min(ans,sum(r))
lx=sum(l)*2
rx=sum(r)*2
for i in range(1,k):
    if rr-i>0 and i<=ll and min(i,ll)+(rr-i)>=k:
        lx=lx-(l[-i]*2)+r[i-1]
        ans=min(ans,lx)
    if ll-i>0 and i<=rr and min(i,rr)+(ll-i)>=k:
        rx=rx-(r[-i]*2)+l[i-1]
        ans=min(ans,rx)
print(ans)

n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]

ll=len(l)
rr=len(r)
lx=sum(l)
rx=sum(r)

if ll<k: lx=lx*2+sum(r[:(k-ll)])
if rr<k: rx=rx*2+sum(l[:(k-rr)])
ans=min(lx,rx)
print(ans)
o=[ll,[0,k-ll][ll<k]]
p=[rr,[0,k-rr][rr<k]]

"""
-30 -10 10 20 50
print(o)
print(p)
[2, 1]
[3, 0]
"""

for i in range(1,k):
    if o[1]==0: lx*=2
    #if r[1]==0: rx*=2
    if o[1]+1<=rr and o[0]>0:
        lx-=l[o[0]-1]*2
        lx+=r[o[1]]
        o[0]-=1
        o[1]+=1
        ans=min(ans,lx)
    #if p[1]+1<=ll and p[0]>0:
    #    rx-=r[p[0]-1]*2
    #    rx+=l[p[1]]
    #    p[0]-=1
    #    p[1]+=1
    #    ans=min(ans,rx)
print(ans)


n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]
ll=len(l)
rr=len(r)

ans=sum(l)*2+sum(r)*2
if ll==k: ans=min(ans,sum(l))
if rr==k: ans=min(ans,sum(r))
for i in range(1,k):
    if rr>i and len(l[:-i])+i==k: ans=min(ans,(sum(r[:i])+sum(l[:-i])*2))
    if ll>i and len(r[:-i])+i==k: ans=min(ans,(sum(l[:i])+sum(r[:-i])*2))

print(ans)

n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in x:
    if i<0: l.append(-i)
    if i>=0: r.append(i)
l.sort()
r.sort()
l=l[:k]
r=r[:k]
ll=len(l)
rr=len(r)
lx,rx=[],[]
for i in range(ll):
    if i==0: lx.append(l[i])
    else: lx.append(l[i]-l[i-1])
for i in range(rr):
    if i==0: rx.append(r[i])
    else: rx.append(r[i]-r[i-1])

ans=sum(lx)*2+sum(rx)*2
for i in range(ll):
    if k-1==i: ans=min(ans,sum(lx))
    elif i+rr+1>=k: ans=min(ans,sum(lx[:i+1])*2+sum(rx[:k-i-1]))
    print(lx[:i+1],rx[:k-i-1])

for i in range(rr):
    if k-1==i: ans=min(ans,sum(rx))
    elif i+ll+1>=k: ans=min(ans,sum(rx[:i+1])*2+sum(lx[:k-i-1]))
    print(rx[:i+1],lx[:k-i-1])
print(ans)


n,k=map(int,input().split())
x=[int(i) for i in input().split()]
l,r=[],[]
for i in range(n):
    if x[i]<0 and i+1<n: l.append(abs(x[i]-min(x[i+1],0)))
    elif x[i]<0: l.append(-x[i])
    if x[i]>=0 and i>0: r.append(x[i]-max(0,x[i-1]))
    elif x[i]>=0: r.append(x[i])

l=l[::-1]
l=l[:k]
r=r[:k]

ll=len(l)
rr=len(r)
lx=sum(l)
rx=sum(r)

if ll<k: lx=lx*2+sum(r[:(k-ll)])
if rr<k: rx=rx*2+sum(l[:(k-rr)])
ans=min(lx,rx)
o=[ll,[0,k-ll][ll<k]]
p=[rr,[0,k-rr][rr<k]]


for i in range(1,k):
    if o[1]==0: lx*=2
    if p[1]==0: rx*=2
    if o[1]+1<=rr and o[0]>0:
        lx-=l[o[0]-1]*2
        lx+=r[o[1]]
        o[0]-=1
        o[1]+=1
        ans=min(ans,lx)
    if p[1]+1<=ll and p[0]>0:
        rx-=r[p[0]-1]*2
        rx+=l[p[1]]
        p[0]-=1
        p[1]+=1
        ans=min(ans,rx)
print(ans)


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted