Problem p02821 (python)

Fixed submission:
import numpy as np

N ,M= map(int,input().split())
l=list(map(int,input().split()))
n0 = 2**int(np.ceil(np.log2(2*(max(l))-1)))

A = np.zeros(n0)
#B=np.zeros(n0)
#l=list(map(int,input().split()))

for i in range(N):
    A[l[i]-1]+=1
   # B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(A) )
ans=0
j=2
q=[]
for ci in np.real(C[:2*(max(l))-1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
#print(q)
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    z+=q[j][0]
    j+=1
ans-=(z-M)*q[j-1][1]
print(ans)

Buggy submission (verdict: Runtime Error):
import bisect
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
r=[0]*(10**5+2)
for i in range(n):
    r[l[i]]+=1
for i in range(10**5+1):
    r[i+1]+=r[i]
ok=10**11
ng=0
while ok-ng>1:
    x=(ok+ng)//2
    k=0
    for i in range(n):
        if x-l[i]<0:
            k+=n
        elif x-l[i]>10**5+1:
            continue
        else:
            k+=r[x-l[i]]
    if k>=m:
        ng=x
    else:
        ok=x
p=[0]*(n+1)
for i in range(n):
    p[i+1]=p[i]+l[i]
ans=0
for i in range(n):
    li=bisect.bisectleft(l,ok-l[i])
    ans+=l[i]*(n-li)+p[n]-p[li]
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

N ,M= map(int,input().split())
l=list(map(int,input().split()))
n0 = 2**int(np.ceil(np.log2(2*(max(l)))))

A = np.zeros(n0)
#B=np.zeros(n0)
#l=list(map(int,input().split()))

for i in range(N):
    A[l[i]]+=1
   # B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(A) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*(max(l))] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
#print(q)
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    z+=q[j][0]
    j+=1
ans-=(z-M)*q[j-1][1]
print(ans-1)

Buggy submission (verdict: Runtime Error):
import numpy as np

N ,M= map(int,input().split())
l=list(map(int,input().split()))
n0 = 2**int(np.ceil(np.log2(2*(max(l)+1) - 1)))

A = np.zeros(n0)
#B=np.zeros(n0)
#l=list(map(int,input().split()))

for i in range(N):
    A[l[i]]+=1
   # B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(A) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*(max(l)+1)- 1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j-1][1]
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

N ,M= map(int,input().split())
l=list(map(int,input().split()))
n0 = 2**int(np.ceil(np.log2(2*(max(l)+1) - 1)))

A = np.zeros(n0)
#B=np.zeros(n0)
#l=list(map(int,input().split()))

for i in range(N):
    A[l[i]]+=1
   # B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(A) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*(max(l)+1)- 1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

N ,M= map(int,input().split())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B=np.zeros(n0)
l=list(map(int,input().split()))

for i in range(N):
    A[i]=l[i]
    B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*N - 1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

N ,M= map(int,input().split())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B=np.zeros(n0)
l=list(map(int,input().split()))

for i in range(N):
    A[i]=l[i]
    B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*N - 1] + 0.5):
    #ans+=int(ci)*j
    q.append([ci,j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Buggy submission (verdict: Runtime Error):
import numpy as np

N = int(input())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B = np.zeros(n0)
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
for ci in np.real(C[:2*N - 1] + 0.5):
    ans+=int(ci)*j
    j+=1
print(ans)