Problem p03038 (python)

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = ind + l[1] -1 
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    #temp = A[now:now+C_B[j][1]]
    #print(temp)
    X=min(now+C_B[j][1], N-1)
    if C_B[j][0]>=A[X]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
        if now>=N:
            break
    elif C_B[j][0]<=A[now]: #置き換えない
        break
    else:
        sm = now
        la = now+C_B[j][1]-1
        md = now+C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            
            if A[md]<p:
                sm=md
                md=(la-sm)//2
            elif A[md]==p:
                la=md
            else:
                la=md-1
                md=(la-sm)//2
        sums += (la-now)*p
        now = la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    #temp = A[now:now+C_B[j][1]]
    #print(temp)
    if C_B[j][0]>=A[now+C_B[j][1]]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
    elif C_B[j][0]<=A[now]: #置き換えない
        break
    else:
        sm = now
        la = C_B[j][1]-1
        md = C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            if A[now+md]<p:
                sm=md
                md=(la-sm)//2
            elif A[now+md]==p:
                la=md
            else:
                la=md-1
                md=(la-sm)//2
        sums += la*p
        now += la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    temp = A[now:now+C_B[j][1]]
    #print(temp)
    if C_B[j][0]>=temp[-1]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
    elif C_B[j][0]<=temp[0]: #置き換えない
        break
    else:
        sm = 0
        la = len(temp)-1
        md = C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            if temp[md]<p:
                sm=md
                md=(la-sm)//2
            elif temp[md]==p:
                la=md
            else:
                la=md
                md=(la-sm)//2
        sums += la*p
        now += la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

C_B = []
for _ in range(M):
    B, C = map(int, input().split())
    C_B.append([C, B])
C_B.sort(reverse = True)

sums = 0
now = 0
for j in range(M):
    temp = A[now:now+C_B[j][1]]
    #print(temp)
    if C_B[j][0]>=temp[-1]: #すべて置き換え
        sums += C_B[j][0]*C_B[j][1]
        now += C_B[j][1]
    elif C_B[j][0]<=temp[0]: #置き換えない
        break
    else:
        sm = 0
        la = len(temp)-1
        md = C_B[j][1]//2
        p = C_B[j][0]
        while la-sm>1:
            if temp[md]<p:
                sm=md
                md=(la-sm)//2
            elif temp[md]==p:
                la=md
            else:
                la=md
                md=(la-sm)//2
        sums += la*p
        now += la
        break
#print(sums, now)
#残りを加算
if now<=N:
    for i in range(now, N):
        sums += A[i]
print(sums)