Problem:


Score : 500 points

Problem Statement

There are N cards. The i-th card has an integer A_i written on it.
For any two cards, the integers on those cards are different.

Using these cards, Takahashi and Aoki will play the following game:

Aoki chooses an integer x.

Starting from Takahashi, the two players alternately take a card. The card should be chosen in the following manner:

Takahashi should take the card with the largest integer among the remaining card.

Aoki should take the card with the integer closest to x among the remaining card. If there are multiple such cards, he should take the card with the smallest integer among those cards.

The game ends when there is no card remaining.

You are given Q candidates for the value of x: X_1, X_2, ..., X_Q.
For each i (1 \leq i \leq Q), find the sum of the integers written on the cards that Takahashi will take if Aoki chooses x = X_i.

Constraints

2 \leq N \leq 100 000

1 \leq Q \leq 100 000

1 \leq A_1 < A_2 < ... < A_N \leq 10^9

1 \leq X_i \leq 10^9 (1 \leq i \leq Q)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 ... A_N
X_1
X_2
:
X_Q

Output

Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer for x = X_i.

Sample Input 1

5 5
3 5 7 11 13
1
4
9
10
13

Sample Output 1

31
31
27
23
23

For example, when x = X_3(= 9), the game proceeds as follows:

Takahashi takes the card with 13.

Aoki takes the card with 7.

Takahashi takes the card with 11.

Aoki takes the card with 5.

Takahashi takes the card with 3.

Thus, 13 + 11 + 3 = 27 should be printed on the third line.

Sample Input 2

4 3
10 20 30 40
2
34
34

Sample Output 2

70
60
60



Sample input:
5 5
3 5 7 11 13
1
4
9
10
13


Sample output:
31
31
27
23
23

Submission status: Runtime Error

Solution code:
import bisect
from itertools import accumulate
from operator import add
from math import ceil

n, q = map(int, input().split())
alist = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())

alist = sorted(alist)
upper_sum = list(accumulate(alist[::-1], add))
if n % 2 == 0:
    lower_sum = list(accumulate(alist[1::2], add))
else:
    lower_sum = list(accumulate(alist[::2], add))

for x in xnum:
    xpos = bisect.bisect(alist, x)
    cnt = 0
    aoki_card = sorted(alist, key=lambda a: (abs(a-x), a))
    for i, ac in enumerate(aoki_card):
        if ac > x:
            cnt += 1
        if i+1 + cnt >= n-xpos:
            break
    i += 1
    print(upper_sum[i-1] + (lower_sum[ceil((n-2*i)/2)-1] if 2*i < n else 0))

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
alist = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())

alist = sorted(alist)
upper_sum = list(accumulate(alist[::-1], add))
if n % 2 == 0:
    lower_sum = list(accumulate(alist[1::2], add))
else:
    lower_sum = list(accumulate(alist[::2], add))

for x in xnum:
    xpos = bisect.bisect(alist, x)
    cnt = 0
    aoki_card = sorted(alist, key=lambda a: (abs(a-x), a))
    for i, ac in enumerate(aoki_card):
        if ac > x:
            cnt += 1
        if i+1 + cnt >= n-xpos:
            break
    i += 1
    print(upper_sum[i-1] + (lower_sum[ceil((n-2*i)/2)-1] if 2*i < n else 0))

Submission status: Runtime Error

Solution code:
import bisect
from itertools import accumulate
from operator import add
from math import ceil

n, q = map(int, input().split())
alist = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())

upper_sum = list(accumulate(alist[::-1], add))
if n % 2 == 0:
    lower_sum = list(accumulate(alist[1::2], add))
else:
    lower_sum = list(accumulate(alist[::2], add))

for x in xnum:
    xpos = bisect.bisect(alist, x)
    cnt = 0
    aoki_card = sorted(alist, key=lambda a: (abs(a-x), a))
    for i, ac in enumerate(aoki_card):
        if ac > x:
            cnt += 1
        if i+1 + cnt >= n-xpos:
            break
    i += 1
    print(upper_sum[i-1] + (lower_sum[ceil((n-2*i)/2)-1] if 2*i < n else 0))

Submission status: Runtime Error

Solution code:
import bisect
from itertools import accumulate
from operator import add
from math import ceil

n, q = map(int, input().split())
alist = list(map(int, input().split()))
xnum = [0]*q
for i in range(q):
    xnum[i] = int(input())

upper_sum = list(accumulate(alist[::-1], add))
if n % 2 == 0:
    lower_sum = list(accumulate(alist[1::2], add))
else:
    lower_sum = list(accumulate(alist[::2], add))

for x in xnum:
    xpos = bisect.bisect(alist, x)
    cnt = 0
    aoki_card = sorted(alist, key=lambda a: (abs(a-x), a))
    for i, ac in enumerate(aoki_card):
        if ac > x:
            cnt += 1
        if i+1 + cnt >= n-xpos:
            break
    i += 1
    print(upper_sum[i-1] + (lower_sum[ceil((n-2*i)/2)-1] if 2*i < n else 0))

Submission status: Runtime Error

Solution code:
import bisect

N,Q=map(int,input().split())
alist=list(map(int,input().split()))
#print(alist)

ans_list=[0]*(alist[-1]+1)
for i in range(1,alist[-1]+1):
  alist_copy = list(alist)
  t_score = 0
  a_score = 0
  
  while(True):
    if len(alist_copy)>0:
      t_score += alist_copy[-1]
      alist_copy.pop()
    else:
      ans_list[i] = t_score
      break

    if len(alist_copy)>0:
      index = bisect.bisect_left(alist_copy,i)
      #print((i,alist_copy,index))
      if index == 0:
        a_score += alist_copy[0]
        alist_copy.pop(0)
      elif index == len(alist_copy):
        a_score += alist_copy[-1]
        alist_copy.pop()
      else:
        if i-alist_copy[index-1] <= alist_copy[index]-i:
          a_score += alist_copy[index-1]
          alist_copy.pop(index-1)
        else:
          a_score += alist_copy[index]
          alist_copy.pop(index)
    else:
      ans_list[i] = t_score
      break
  
#print(ans_list)
for i in range(Q):
  print(ans_list[int(input())])

Submission status: Runtime Error

Solution code:
import numpy as np
def gV(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def nea(n,q,a,x):
    aa=a[:]
    taka=0
    for z in range(q):
        for i in range(n):
            if a[-i-1]==999999:
                pass
            else:
                taka+=a[-i-1]
                a[-i-1]=999999
                a[gV(a,x[z])]=999999
        print(taka)
        a=aa[:]
        taka=0
    exit()
n,q=map(int,input().split())
print(nea(n,q,list(map(int,input().split())),[int(input()) for i in range(q)]))

Submission status: Runtime Error

Solution code:
import numpy as np
def gV(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def nea(n,q,a,x):
    aa=a[:]
    taka=0
    for z in range(q):
        for i in range(n):
            if a[-i-1]==999999:
                pass
            else:
                taka+=a[-i-1]
                a[-i-1]=999999
                a[gV(a,x[z])]=999999
        print(taka)
        a=aa[:]
        taka=0

    exit()

n,q=map(int,input().split())
print(nea(n,q,list(map(int,input().split())),[int(input()) for i in range(q)]))

Submission status: Runtime Error

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168

import bisect

N,Q=map(int,input().split())

A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0

for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

X=[] 
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

Submission status: Runtime Error

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168

import sys
input = sys.stdin.readline

import bisect

N,Q=map(int,input().split())

A=list(map(int,input().split()))

Asum=[0]*N
Asum2=[0]*N
total=0
X=[]
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]
    
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break;
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue;
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

Submission status: Runtime Error

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168
import bisect
N,Q=map(int,input().split())
A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0
X=[]
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]
    
for i in range(Q):
  X.append((int(input()),i))
X.sort(key=lambda x :x[0])
  

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
#Xを小さい順から計算することで、yの値が単調増加になる
y=N//2-1
ans=[0]*Q
for x,i in X:
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break;
  #右端からA[y]までは全て高橋くんが取る
  ans[i]+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    continue;
  ans[i]+=Asum2[y-(N-y)-1]

for i in range(Q):
  print(ans[i])

Submission status: Runtime Error

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168
import bisect
N,Q=map(int,input().split())
A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0
total2=0
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る
y=N//2-1

for i in range(Q):
  
  ans=0
  x=int(input())
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break;
      #右端からA[y]までは全て高橋くんが取る
  ans+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    print(ans)
    continue;
  ans+=Asum2[y-(N-y)-1]
  
  print(ans)

Submission status: Runtime Error

Solution code:
#参考
#https://atcoder.jp/contests/aising2019/submissions/3995168
import bisect
N,Q=map(int,input().split())
A=list(map(int,input().split()))
Asum=[0]*N
Asum2=[0]*N
total=0
total2=0
for i in range(N):
  total+=A[i]
  Asum[i]=total
  if i>1:
    Asum2[i]=A[i]+Asum2[i-2]
  else:
    Asum2[i]=A[i]

#yで高橋くんと青木くんの取りたいカードが初めて衝突すると考える。
#このようなyは半分より小さい所にはないので初期値を半分のところとする。
#yがNまで来た時は最初から交互に取る

for i in range(Q):
  y=N//2-1
  ans=0
  x=int(input())
  while x>A[y] and y<=N-1:
    y+=1
  while y<=N-1:
    takahashi=N-y
    aoki=y+1-bisect.bisect_left(A,x-(A[y]-x))
    if takahashi>aoki:
      y+=1
    else:
      break;
      #右端からA[y]までは全て高橋くんが取る
  ans+=Asum[N-1]-Asum[y-1]
  #青木くんはyからN-y個取っているので、その下のところから交互に取る
  if y-(N-y)-1<0:
    print(ans)
    continue;
  ans+=Asum2[y-(N-y)-1]
  
  print(ans)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

# 整数Xのときの[高橋くんが上から取る連続枚数]が、k枚以下（k+1以上にはならない）かどうか判定する
def check(X, k):
    # 青木くんがLより先にRを取れれば、条件を満たす
    L, R = As[N-2*k-1], As[N-k-1]
    return abs(L-X) > abs(X-R)

N, Q = map(int, input().split())
As = list(map(int, input().split()))
Xs = [(int(input()), iX) for iX in range(Q)]

numT = (N+1) // 2  # 高橋くんが取るカードの枚数
Ascs = As[::2] if N % 2 else As[1::2]
Descs = As[::-1]
accAscs = [0] + list(accumulate(Ascs))
accDescs = [0] + list(accumulate(Descs))

# 高橋くんが上から連続k枚を取る場合のスコア
scores = [0] * (numT+1)
for k in range(1, numT+1):
    scores[k] = accDescs[k] + accAscs[numT - k]

# Xの降順で処理する
anss = [0] * Q
k = 1
for X, iX in sorted(Xs, reverse=True):
    # [k枚以下]になる最小のkを求める
    while not check(X, k):
        k += 1
    anss[iX] = scores[k]

print('\n'.join(map(str, anss)))

Submission status: Runtime Error

Solution code:
def d_nearest_card_game(N, Q, A, X):
    # 最初は、高橋くんは数字の大きなカードを、青木くんはxに近いものから取っていく。
    # するといつか高橋くんが取りたいカードが青木くんに取られているような状況になるので、
    # そこからは2人で値の大きなものから順に取っていく。
    # そのため、2人で順に取っていく領域の広さ(N/2通り)がわかればいい。
    # N/2通りなのは、順に取っていくフェイズの前に2人がそれぞれ固まった領域の
    # カードを取るフェイズがN/2回あるため。
    # (Nが偶数のとき。奇数のときは両者が両端から取っていって
    # 最後に高橋くんが真ん中のカードを取ることがありうる)

    # これらの場合について、境界となるxの値を先に求めておけば、各クエリに対して
    # どの場合に当たるのかを高速に判定できる。

    # 境界となるxは青木くんがまとめて取ることになる領域の左右端の中央にある。
    # 数列のインデックスを右から0-basedで付けていくと、
    # 高橋くんがまとめて取っている領域は 0, 1, ..., i
    # 青木くんがまとめて取っている領域は i+1, i+2, ..., 2i+1
    # 境界となるxは (A[i+1]+A[2i+2])//2 + 1

    # iの値が分かったときに高橋くんの得点を求めるには、
    # Aの累積和とAの右から偶数番目だけ取る累積和を求めておけばいい。
    import bisect

    a = A[::-1]  # 「右から」はわかりづらいので逆にする
    # 累積和と偶数番目だけ足す累積和
    cumsum, evensum = [0] * (N + 1), [0] * (N + 1)
    for k, a_k in enumerate(a):
        cumsum[k + 1] = cumsum[k] + a_k
        evensum[k + 1] = evensum[k] + (a_k if k % 2 == 0 else 0)

    # 得点が変化するxの境界とそのときの得点
    threshold, threshold_score = [], []
    for k in range((N - 1) // 2):
        threshold.append((a[k + 1] + a[2 * k + 2]) // 2 + 1)
        threshold_score.append((cumsum[k + 1] - cumsum[0]) + (evensum[N] - evensum[2 * k + 2]))

    # Aを逆にしたので、もう一度逆にする
    threshold = threshold[::-1]
    threshold_score = threshold_score[::-1]

    ans = []
    for x in X:
        idx = bisect.bisect_right(threshold, x)
        if idx == 0:
            ans.append(cumsum[(N + 1) // 2] - cumsum[0])
        else:
            ans.append(threshold_score[idx - 1])
    ans = '\n'.join(map(str, ans))
    return ans

A = [int(i) for i in input().split()]
X = [int(input()) for _ in range(Q)]
print(d_nearest_card_game(N, Q, A, X))

Submission status: Runtime Error

Solution code:
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    elif x <= A[0]:
        return (N+1)//2
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        return chk(x, l, (l+m)//2, m)
    else:
        return max(N - rr - 1, 1)
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Submission status: Runtime Error

Solution code:
N, Q = list(map(int, input().split(" ")))
A_list = list(map(int, input().split(" ")))

def game(A_list, X, N):
    aoki_A_list = sorted(A_list, key=lambda val: abs(val-X))

    count = 0
    aoki_last_plus = None 
    aoki_minus_plus = None
    aoki_last_minus = None
    while True:
        taka_val = A_list[-count-1]
        aoki_val = aoki_A_list[count]
        aoki_view_val = aoki_val - X

        if aoki_view_val >= 0:
            aoki_last_plus = aoki_val
            now_plus = True
        else:
            now_plus = False

        #print(taka_val, aoki_val, aoki_last_plus, aoki_view_val)

        if aoki_last_plus is not None and aoki_last_plus >= taka_val:
            if not now_plus:
                aoki_fail = False
            if now_plus:
                if aoki_last_plus == taka_val:
                    aoki_fail = True
                else:
                    aoki_fail = False

            break

        if aoki_view_val < 0:
            aoki_last_minus = aoki_val
        
        count += 1

    conflict_count = count

    first_sum = sum(aoki_A_list[:conflict_count])
    if aoki_last_minus is not None:
        aoki_minus_last_i = A_list.index(aoki_last_minus)
    else:
        if conflict_count >= 1:
            aoki_minus_last_i = A_list.index(aoki_A_list[0])
        else:
            aoki_minus_last_i = None

    last_i = aoki_minus_last_i
    if last_i is not None:
        if aoki_fail:
            if last_i >= 1:
                if last_i % 2 == 1:
                    nokori_sum = sum(A_list[0:last_i:2])
                else:
                    nokori_sum = sum(A_list[1:last_i:2])
                
            else:
                nokori_sum = 0
        else:
            if last_i >= 2:
                nokori_sum = sum(A_list[(last_i%2):last_i-1:2])
            else:
                nokori_sum = 0

        out = sum(A_list) - (first_sum + nokori_sum)
    else:
        if N % 2 == 1:
            out = sum(A_list[0::2])
        else:
            out = sum(A_list[1::2])

    return out
        
for i in range(Q):
    X = int(input())
    out = game(A_list, X, N)
    print(out)

Submission status: Runtime Error

Solution code:
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    elif x <= A[0]:
        return (N+1)//2
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return max(N - rr - 1, 1)
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
a = list(map(int, input().split()))
x = [int(input()) for _ in range(q)]
sort_x = sorted(x)
ans = {}
len_x = len(a)
flag = True
if len_x%2== 1:
    small_position = 0
    border_position = int((len_x-1)/2)
    sum_all = sum(a[border_position:])
    a.append(1000000000)
    for x_i in sort_x:
        for compare in a[border_position:]:
            if x_i - a[small_position] > compare-x_i:
                sum_all = sum_all + a[small_position] - compare
                small_position += 2
                border_position += 1
                ans[x_i] = sum_all
            else:
                ans[x_i] = sum_all
                break

else:
    small_position = 1
    border_position = int(len_x/2)
    sum_all = sum(a[border_position:])
    a.append(1000000000)
    for x_i in sort_x:
        for compare in a[border_position:]:
            if x_i - a[small_position] > compare-x_i:
                sum_all = sum_all + a[small_position] - compare
                small_position += 2
                border_position += 1
                ans[x_i] = sum_all
            else:
                ans[x_i] = sum_all
                break

for x_i in x:
    print(ans[x_i])

Submission status: Runtime Error

Solution code:
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return N - rr - 1
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Submission status: Runtime Error

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import bisect
import heapq
import math


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    X = [int(input()) for i in range(q)]

    ss = [0] * (n+1)
    odd = [0] * (n+1)
    even = [0] * (n+1)

    for i in range(n):
        ss[i+1] = ss[i] + a[i]
        if i % 2:
            odd[i+1] = odd[i-1] + a[i]
        else:
            if i == 0:
                even[i+1] = a[i]
            else:
                even[i+1] = even[i-1] + a[i]

    dic = {}
    for i in range(n):
        dic[a[i]] = i

    for x in X:
        idx = bisect.bisect_left(a, x)
        if idx and abs(a[idx-1]-x) <= abs(a[idx]-x):
            idx -= 1

        left, right = idx - 1, len(a)
        while 1 < right - left:
            mid = (left+right) // 2
            dif = a[mid] - x
            j = bisect.bisect_left(a, x - dif)
            t = mid - j + 1
            if t < n - mid:
                left = mid
            else:
                right = mid

        d = max(0, 2*left-n+2)
        ans = ss[n] - ss[max(n-1, left+1)]
        if d % 2 == 0:
            ans += odd[d]
        else:
            ans += even[d]

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


N, Q = map(int, input().split())
A = [int(s) for s in input().split()]
X = []
for _ in range(Q):
    X.append(int(input()))

A.sort()
s = [0] * (N + 1)
for i in range(N + 1):
    s[i] = s[i - 1] + x[i - 1]
t = [0, A[0]] + [0] * (N - 1)
for i in range(N):
    t[i] = t[i - 2] + A[i - 1]


def index_hidari(x, i):
    val = 2 * x - A[i]
    return bisect_left(A, val)

# x <= A[i]


def nankaime(x, i):
    return i - index_hidari(x, i) + 1


def npi(x, i):
    return nankaime(x, i) + i


def index_migi(x, istart):
    ls = LazySequence(lambda i: npi(x, i + istart), N - istart)
    return istart + bisect_left(ls, N) - 1


def getans(x):
    istart = bisect_left(A, x)
    if istart = N:
        return t[N]
    j = index_migi(x, istart)
    turn = N - 1 - i
    i = j - turn
    return t[i - 1] + s[N] - s[j + 1]


for i in range(Q):
    print(getans(X[i]))

Submission status: Runtime Error

Solution code:
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return (m+1)//2
    
    
Y = [0] * N
for i in range(1, N):
    Y[i] = Y[i-1] + A[-i-1]

Z = [0] * N
for i in range(1, N):
    Z[i] = Z[i-1] + A[((1+N)%2)::2]

for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    print(Y[t]+Z[N-t])

Submission status: Runtime Error

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import bisect
import heapq
import math


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    X = [int(input()) for i in range(q)]

    ss = [0] * (n+1)
    odd = [0] * (n+1)
    even = [0] * (n+1)

    for i in range(n):
        ss[i+1] = ss[i] + a[i]
        if i % 2:
            odd[i+1] = odd[i-1] + a[i]
        else:
            if i == 0:
                even[i+1] = a[i]
            else:
                even[i+1] = even[i-1] + a[i]

    dic = {}
    for i in range(n):
        dic[a[i]] = i

    for x in X:
        idx = bisect.bisect_left(a, x)
        if idx and abs(a[idx-1]-x) <= abs(a[idx]-x):
            idx -= 1

        left, right = idx - 1, len(a)
        while 1 < right - left:
            mid = (left+right) // 2
            dif = a[mid] - x
            j = bisect.bisect_left(a, x - dif)
            t = mid - j + 1
            if t < n - mid:
                left = mid
            else:
                right = mid

        d = max(0, 2*left-n+2)
        ans = ss[n] - ss[left+1]
        if d % 2 == 0:
            ans += odd[d]
        else:
            ans += even[d]

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

first=input().split(" ")
board=int(first[0])
times=int(first[1])

BF=input().split(" ")
bf=[]
for i in BF:
    bf.append(int(i))

for i in range(board):
    this=int(input())
    s={}
    for i in range(board):
        s[bf[i]]=(bf[i]-this)*(bf[i]-this)
        
    point=0
    
    for i in range(times):
        sorted(s.items(), key=lambda x: x[0])
        point+=max(s)
        del s[-1]
        if len(s)==0:
            break;
        sorted(s.items(), key=lambda x: x[1])
        del s[0]
        if len(s)==0:
            break;
    print(point)

Submission status: Runtime Error

Solution code:
import numpy as np
def getNearestValue(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx 

N,Q=map(int,input().split())
a= [int(_) for _ in input().split()]
X =[]
for i in range(Q):
    X.append(int(input()))

A = np.array(a)
    
takahasi=0
for i in X:
    A = np.array(a)
    takahasi=0
    count=0
    while(count<=Q/2):
        takahasi = takahasi + max(A)
        A = np.delete(A,A.argmax())
        if(A!=[]):
            j=getNearestValue(A,i)
            A = np.delete(A,j)
        
        count=count+1
    print(takahasi)

Submission status: Runtime Error

Solution code:
N,Q = list(map(int,input().split()))
A = list(map(int,input().split()))
X = []
for i in range(Q):
    X.append(int(input()))

turn = 0
res_T = 0

def take_card(A,x,turn,res_T):
    if len(A) == 0:
        pass
    else:
        if turn%2 == 0:
            res_T += A.pop(-1)
            res_T = take_card(A,x,turn+1,res_T)
        else:
            A_ = [abs(a-x) for a in A]
            _ = A.pop(A_.index(min(A_)))
            res_T = take_card(A,x,turn+1,res_T)
    return res_T

for x in X:
    print(take_card(A.copy(), x, 0, res_T))

Submission status: Runtime Error

Solution code:
import numpy as np
N, Q = map(int, input().split())
A = input().split()

i = 0
X = []
takaanswer = 0
aokianswer = 0
k = 1

for i in range(Q):
    X.append(int(input()))

def taka():
    takaanswer = X.pop()

def aoki(k):
    i = np.abs(np.asarray(X)-k).argmin()
    aokianswer += X[k]
    X.remove(aokianswer)


for a in A:
    taka()
    aoki(a)
    print(takaanswer)

Submission status: Runtime Error

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-

from collections import deque
import bisect
import heapq
import math


def main():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    X = [int(input()) for i in range(q)]

    ss = [0] * (n+1)
    odd = [0] * (n+1)
    even = [0] * (n+1)

    for i in range(n):
        ss[i+1] = ss[i] + a[i]
        if i % 2:
            odd[i+1] = odd[i-1] + a[i]
        else:
            if i == 0:
                even[i+1] = a[i]
            else:
                even[i+1] = even[i-1] + a[i]

    dic = {}
    for i in range(n):
        dic[a[i]] = i

    for x in X:
        idx = bisect.bisect_left(a, x)
        if idx and abs(a[idx-1]-x) <= abs(a[idx]-x):
            idx -= 1

        left, right = idx - 1, len(a)
        while 1 < right - left:
            mid = (left+right) // 2
            dif = a[mid] - x
            j = bisect.bisect_left(a, x - dif, 0, mid)
            t = mid - j + 1
            if t < n - mid:
                left = mid
            else:
                right = mid

        d = max(0, 2*left-n+2)
        ans = ss[n] - ss[left+1]
        if d % 2 == 0:
            ans += odd[d]
        else:
            ans += even[d]

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
A = input().split()

i = 0
X = []
takaanswer = 0
aokianswer = 0
k = 1

for i in range(Q):
    X.append(int(input()))

def taka():
    takaanswer = X.pop()

def aoki(k):
    aokianswer += X[k]
    X.remove(aokianswer)


for a in A:
    taka()
    aoki(a)

Submission status: Runtime Error

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

import sys
import bisect

sys.setrecursionlimit(10000)

N, Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
X = []
for _ in range(Q):
    X.append(int(input()))

A.sort()
A_COPY = A.copy()

T = []


def takahashi():
    a = A[-1]
    T.append(a)
    del A[-1]


def aoki(x):
    l = bisect.bisect_left(A, x) - 1
    idx = l
    if l == len(A):
        idx = l - 1
    elif l + 1 < len(A):
        if abs(A[l] - x) > abs(A[l + 1] - x):
            idx = l + 1
    del A[idx]


for x in X:
    A = A_COPY.copy()
    T = []
    while True:
        takahashi()
        if len(A) == 0:
            break
        aoki(x)
        if len(A) == 0:
            break
    print(sum(T))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
A = input().split()

i = 0
X = []
takaanswer = 0
aokianswer = 0

for i in range(Q):
    X.append(int(input()))

def taka():
    takaanswer = X.pop()

def aoki(TX, tx):
    aokianswer += TX[tx]
    X.remove(aokianswer)


for a in A:
    taka()
    aoki(X,a)

Submission status: Runtime Error

Solution code:
def nibun(v, k):
  n = len(k)
  if n == 2:
    return 1
  elif v < k[n//2]:
    return nibun(v, k[:n//2+1])
  else:
    return n//2 + nibun(v, k[n//2:])

n, q = map(int, input().split())
a = list(map(int, input().split()))

s = [0] * (n //2 + n%2)
x = [0] * (n // 2 + n % 2 - 1)
s[0] = sum(a[n // 2:])
if n % 2 == 0:
  for i in range(1, len(s)):
    s[i] = s[i-1] + a[2 * i -1] - a[n // 2 + i - 1]
    x[i-1] = (a[2*i-1] + a[n//2+i-1]) // 2
else:
  for i in range(1, len(s)):
    s[i] = s[i-1] - a[n//2+i-1] + a[2*(i-1)]
    x[i-1] = (a[2*(i-1)]+a[n//2+i-1]) // 2

for j in range(q):
  v = int(input())
  if n == 1:
    print(s[0])
  elif v > x[len(x)-1]:
    print(s[-1])
  elif v <= x[0]:
    print(s[0])
  else:
    i = nibun(v, x)
    print(s[i])