Problem p02821 (python)

Fixed submission:
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*110000
a_sum = [0]*110000

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        case += n-bisect_right(a,x-a[i]-1)
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left
from bisect import bisect_right

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

a_count = [0]*100010
a_sum = [0]*100010

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,-1,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if 0<= x-a[i]:
            case += a_count[x-a[i]]
        else:
            case += n
    if case >= m:
        ch = True
    else:
        ch = False
    return ch

l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

a_count = [0]*110000
a_sum = [0]*110000

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

from bisect import bisect_left
from bisect import bisect_right

case = 0
for i in range(n):
    num = n-bisect_right(a,l-a[i]-1)
    case += num
    ans += num*a[i]*2

ans -= (case-m)*l

print(ans)

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

a_count = [0]*110000
a_sum = [0]*110000

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 2*a[-1]+1    #NG
r = 1 #OK

while abs(r-l) > 1:
    kk = (r+l)//2
    if chk(kk):
        r = kk
    else:
        l = kk

ans = 0
sm = sum(a)

l = r

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += a_count[l-a[i]]*a[i] + a_sum[l-a[i]]

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += a_count[l-a[i]]

ans -= (case-m)*l

print(ans)

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

a_count = [0]*110000
a_sum = [0]*110000

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(100005,0,-1):
    a_count[i] += a_count[i+1]
    a_sum[i] += a_sum[i+1]

def chk(x):
    case = 0
    for i in range(n):
        if x-a[i] <= 1:
            case += n
        else:
            case += a_count[x-a[i]]
    if case >= m:
        ch = True
    else:
        ch = False
    return ch


l = 1    #OK
r = 2*10**5 + 1 #NG

while r-l > 1:
    kk = (r+l)//2
    if chk(kk):
        l = kk
    else:
        r = kk

ans = 0
sm = sum(a)

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += a_count[l-a[i]]*a[i] + a_sum[l-a[i]]

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += a_count[l-a[i]]

ans -= (case-m)*l

print(ans)

Buggy submission (verdict: Runtime Error):
n,m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

a_count = [0]*100100
a_sum = [0]*100100

for i in range(n):
    a_count[a[i]] += 1
    a_sum[a[i]] += a[i]

for i in range(1,100100):
    a_count[i] = a_count[i] + a_count[i-1]
    a_sum[i] = a_sum[i] + a_sum[i-1]

def chk(x):
    case = 0
    for i in range(n):
        if x-a[i] <= 1:
            case += n
        else:
            case += n-a_count[x-a[i]-1]
    if case >= m:
        ch = True
    else:
        ch = False
    return ch

l = 1    #OK
r = 2*10**5 #NG

while r-l > 1:
    kk = (r+l)//2
    if chk(kk):
        l = kk
    else:
        r = kk

ans = 0
sm = sum(a)

for i in range(n):
    if l-a[i] <= 0:
        ans += sm + n*a[i]
    else:
        ans += (n-a_count[l-a[i]-1])*a[i] + sm-a_sum[l-a[i]-1]
        

case = 0
for i in range(n):
    if l-a[i] <= 1:
        case += n
    else:
        case += n-a_count[l-a[i]-1]

ans -= (case-m)*l

print(ans)