Problem:


Score : 500 points

Problem Statement

Takahashi has come to a party as a special guest.
There are N ordinary guests at the party. The i-th ordinary guest has a power of A_i.

Takahashi has decided to perform M handshakes to increase the happiness of the party (let the current happiness be 0).
A handshake will be performed as follows:

Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).

Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).

What is the maximum possible happiness after M handshakes?

Constraints

1 \leq N \leq 10^5

1 \leq M \leq N^2

1 \leq A_i \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the maximum possible happiness after M handshakes.

Sample Input 1

5 3
10 14 19 34 33

Sample Output 1

202

Let us say that Takahashi performs the following handshakes:

In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.

In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.

In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.

Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202.

We cannot achieve the happiness of 203 or greater, so the answer is 202.

Sample Input 2

9 14
1 3 5 110 24 21 34 5 3

Sample Output 2

1837

Sample Input 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

Sample Output 3

8128170



Sample input:
5 3
10 14 19 34 33


Sample output:
202

Submission status: Runtime Error

Solution code:
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))
a.sort()
l, r = 0, 10000000000
while r - l > 1:
    m = (l + r) // 2
    res = n * n - a.searchsorted(m - a).sum()
    if res >= k:
        l = m
    else:
        r = m
b = np.array([0] * (n + 1))
for i in range(1, n + 1):
    b[i] = b[i - 1] + a[n - i]
cnt = 0
ans = 0
for x in a:
    t = n - bisect_left(a, l - x)
    ans += b[t] + x * t
    cnt += t
print(ans - (cnt - k) * l)

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(200200)

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a - 1].append((b - 1, i))
    E[b - 1].append((a - 1, i))

X = [0] * N

def dfs(u, p):
    X[p] = 1 + sum(dfs(v, c) for v, c in E[u] if p != c)
    return X[p]

dfs(0, -1)

I = [1] * (N + 1)
inv = pow(2, mod - 2, mod)
for i in range(N):
    I[i + 1] = I[i] * inv % mod

ans = (I[N] + 1) * (N - 1) - inv * N - I[N] + 1
for e in range(N - 1):
    ans -= I[X[e]] + I[N - X[e]]
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
l = list(map(int,input().split()))
l.sort(reverse=True)

l_power=[]
for i in range(int(M**(1/2))+1):
  for j in range(int(M**(1/2))+1):
    l_power.append(l[i]+l[j])
l_power.sort(reverse=True)
l_shake = l_power[:M]

print(sum(l_shake))

Submission status: Runtime Error

Solution code:
import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,readline().split())
a = np.array(read().split(),np.int64)

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)

Submission status: Runtime Error

Solution code:
n, m = input().split()
a = [int(_) for _ in input().split()]

ans = []

for a1 in a:
    for a2 in a:
        ans += [a1 + a2]

ans.sort(reverse=True)

print(sum(ans[0:m]))

Submission status: Runtime Error

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++


def count_al(al, vv):
	'''
	vvv以上を集めた場合、何要素選択されるか。
	'''
	rui=0
	for v in al:
		r = get_ok_index(v, al, vv)
		rui += r
	return rui

def get_ok_index(v,al,ok_value):
	'''
	ok_value以上の要素数を返す。
	'''
	if v+al[0] < ok_value:
		return 0
	if v + al[-1] >= ok_value:
		return len(al)
	ok=0
	ng=len(al)
	while ok + 1 < ng:
		#pa((ok,ng))
		m=(ok+ng)//2
		if v+al[m] >= ok_value:
			ok = m
		else:
			ng = m
		#pa((ok,ng))
	return ok+1
	

def main():
	n, m = IN()
	al = list(IN())
	al.sort(reverse=True)
	if m == n*n:
		ret= sum(al) * n * 2
	
	ruisekiwa=al.copy()
	for i,v in enumerate(al[1:],1):
		ruisekiwa[i]=ruisekiwa[i-1]+v
	pa(ruisekiwa)
		
	ok=al[0]*10
	ng=0
	
	while ok  > ng + 1:
		vv = (ok + ng)//2
		cc = count_al(al, vv)
		pa(('ok,ng,vv,cc',ok,ng,vv,cc))
		if cc <= m:
			ok = vv
		else:
			ng = vv
	pa(('ok',ok))
	
	ret=0
	for v in al:
		ok_id = get_ok_index(v, al, ok)-1
		pa(ok_id)
		if ok_id==-1:
			continue
		ret += ruisekiwa[ok_id]+v*(ok_id+1)
	
	ret += (ok - 1)*(m-count_al(al,ok))
	print(ret)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = np.array(lr())
A.sort()
square = A[:, None] + A[None, :]
B = square.flatten()
B.sort()
answer = B[-M:].sum()
print(answer)
# 32

Submission status: Runtime Error

Solution code:
args=input().split()
N=int(args[0])
M=int(args[1])
A=list(map(int,input().split()))
#A.sort(reverse=True)
TEN=[]
for i in range(len(A)-1):
  for j in range(i+1,len(A)):
    TEN.append(A[i]+A[j])
    TEN.append(A[i]+A[j])
  TEN.append(A[i]+A[i])
TEN.sort(reverse=True)
#print(TEN)
res=0
for i in range(M):
  res+=TEN[i]
print(res)

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
ai = list(map(int,input().split()))
 
ai = sorted(ai, reverse=True)
 
def score(ai, k):
    nankai = min( len(ai) * 2 -1  ,k)
    inx = int(nankai /2)
 
    s = (ai[0] * (inx  + 1)  + sum(ai[0:inx + 1]) ) * 2 - 2 * ai[0]  
    s -=  (ai[inx] + ai[0]  if  nankai %2 == 0 and nankai !=0 else 0)
    k-=nankai
    if k > 0:
        return score(ai[1:],k) + s
    return s
 
print(score(ai,m))

Submission status: Runtime Error

Solution code:
import bisect

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

# ある値以上のAiがいくつあるかの情報を累積和で保持
num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(1, 10**5):
  j = 10**5 - i
  num_A_or_more[j-1] += num_A_or_more[j]


# x以上となる手の組み合わせがM種類以上あるかどうかを判定
def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


# 2分探索でM種類以上の手の組み合わせがある満足度の最大値を求める
left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

# これがM種類以上の手の組み合わせがある満足度の最大値
x = left


# 降順に並べなおして累積和を求めておく
rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 # M種類を超えた場合は、一番小さくなる握手の組を最後に削る
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Submission status: Runtime Error

Solution code:
import bisect

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

# ある値以上のAiがいくつあるかの情報を累積和で保持
num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(len(num_A_or_more)-1, 0, -1):
  num_A_or_more[i-1] += num_A_or_more[i]


# x以上となる手の組み合わせがM種類以上あるかどうかを判定
def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


# 2分探索でM種類以上の手の組み合わせがある満足度の最大値を求める
left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

# これがM種類以上の手の組み合わせがある満足度の最大値
x = left


# 降順に並べなおして累積和を求めておく
rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 # M種類を超えた場合は、一番小さくなる握手の組を最後に削る
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Submission status: Runtime Error

Solution code:
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(10**5-1, 0, -1):
  num_A_or_more[i-1] += num_A_or_more[i]


def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Submission status: Runtime Error

Solution code:
def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(ls,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      if hsnum(mx+1) < m:
        error = hsnum(mx)-m
        lx = mx
        break
      lx = mx + 1
    else:
      lx = mx
      break
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i+suma[n]-suma[j]
  print(ans-error*lx)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
B = [0]*(10**5+1)
for i in A:
    B[i]+=1
import copy
BB = copy.deepcopy(B)
C = convolve(B,BB)
 
m = 0
ans = 0
now = 2*10**5
while m < M:
    if C[now] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now]
        m += C[now]
        now -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
B = [0]*(10**5+1)
for i in A:
    B[i]+=1
    
C = convolve(B,B)
 
m = 0
ans = 0
now = 2*10**5
while m < M:
    if C[now] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now]
        m += C[now]
        now -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
LL = 15*10**4
B = [0]*LL
for i in A:
    B[i-1]+=1
    
C = convolve(B,B)
 
m = 0
ans = 0
now = 2*LL
while m < M:
    if C[now-2] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now-2]
        m += C[now-2]
        now -= 1
print(ans)

Submission status: Runtime Error

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
B = [0]*(10**5)
for i in A:
    B[i-1]+=1
    
C = convolve(B,B)
 
m = 0
ans = 0
now = 2*10**5
while m < M:
    if C[now-2] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now-2]
        m += C[now-2]
        now -= 1
        
        
if N**2==M:
    print(2*N*sum(A))
else:
    print(ans)

Submission status: Runtime Error

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))

B = [0]*(10**5)
for i in A:
    B[i-1]+=1
    
C = convolve(B,B)

m = 0
ans = 0
now = 2*10**5
while m < M:
    if C[now-2] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now-2]
        m += C[now-2]
        now -= 1
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(key=lambda x:-x)

# パワーがi以上の人の数
s = [0 for _ in range(2*a[0]+1)]
for p in a:
    s[p] += 1
for i in range(2*a[0], 0, -1):
    s[i-1] += s[i]

def is_over(x):
    num = 0
    for p in a:
        num += s[max(x-p, 0)]
    return num >= k

ub = 2*a[0]+1
lb = 2*a[-1]
while ub-lb > 1:
    x = (ub+lb)//2
    if is_over(x):
        lb = x
    else:
        ub = x

# a[0]からa[i]の累積和
t = a[:]
for i in range(1, n):
    t[i] += t[i-1]
ans = 0
for p in a:
    # 左手固定
    u = s[max(x-p, 0)] # 握手すると閾値を超えるひとたち
    if u != 0:
        ans += p*u+t[u-1] # 1人目pとu回握手 + 右手はu人までと握手
        k -= u
ans += lb*k # 閾値上の人の処理
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort(key=lambda x:-x)

# パワーがi以上の人の数
s = [0 for _ in range(2*a[0]+1)]
for p in a:
    s[p] += 1
for i in range(2*a[0], 0, -1):
    s[i-1] += s[i]

def is_over(x):
    num = 0
    for p in a:
        num += s[max(x-p, 0)]
    return num >= k

ub = 2*a[0]
lb = 2*a[-1]
while ub-lb > 1:
    x = (ub+lb)//2
    if is_over(x):
        lb = x
    else:
        ub = x

# a[0]からa[i]の累積和
t = a[:]
for i in range(1, n):
    t[i] += t[i-1]
ans = 0
for p in a:
    # 左手固定
    u = s[max(x-p, 0)] # 握手すると閾値を超えるひとたち
    if u != 0:
        ans += p*u+t[u-1] # 1人目pとu回握手 + 右手はu人までと握手
        k -= u
ans += lb*k # 閾値上の人の処理
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import math
n,m = map(int,input().split())
a_vec = list(map(int,input().split()))
a_vec.sort()


def count_th(a,x_th):
    cnt=0
    score=0
    for i in range(len(a)-1,-1,-1):
        ind=bisect.bisect_left(a,x_th-a[i])
        score=score+sum(a[ind:len(a)])+a[i]*(n-ind)
        cnt=cnt+len(a)-ind
        if ind==len(a):
            break
    return(cnt,score)
    
x_high = a_vec[-1]*2
x_low  = a_vec[0]*2
x_tmp  = a_vec[math.floor(math.sqrt(m))]*2
coef = 0.5
check=0

min_more_cnt=n*n
min_less_cnt=n*n
while check ==0:
    [tmp_cnt,tmp_score]=count_th(a_vec,x_tmp)
    cnt_diff=abs(tmp_cnt-m)
    if cnt_diff ==0:
        break
 
    if tmp_cnt > m:
        x_low=x_tmp
        x_tmp=math.floor(x_high*(1-coef)+x_low*coef)
        if min_more_cnt > cnt_diff:
            min_more_cnt=cnt_diff
            min_more_cnt_score=tmp_score
        
    if tmp_cnt < m:
        x_high=x_tmp
        x_tmp=math.ceil(x_high*(1-coef)+x_low*coef)
        if min_less_cnt > cnt_diff:
            min_less_cnt=cnt_diff
            min_less_cnt_score=tmp_score
         
    if x_high - x_low <3:
        break

[tmp_cnt,tmp_score]=count_th(a_vec,x_tmp)

if m==tmp_cnt:
    final_score=tmp_score
else:
    final_score = min_less_cnt_score + min_less_cnt*(min_more_cnt_score-min_less_cnt_score)/(min_less_cnt+min_more_cnt)
    
print(int(final_score))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

# FFT
# use python3
# a = [a1,a2,a3], b= [b1,b2,b3]
# return [a1b1,a1b2+a2b1,a1a3+a2b2+a3b1,a2b3+a3b2,a3b3]
import numpy as np
def Convolution(a,b):
    bit = (len(a)+len(b)-2).bit_length()
    L = 2**bit
    fa,fb = np.fft.rfft(a,L), np.fft.rfft(b,L)
    c = np.rint(np.fft.irfft(fa*fb,L)).astype(np.int64)
    return c[:len(a)+len(b)-1]

N,M = II()
A = III()

h = [0]*(max(A))
for a in A:
    h[a-1] += 1

conv = [0,0] + Convolution(h,h)
ans = 0
for k in range(2,2*max(A)+1)[::-1]:
    if conv[k]<M:
        ans += k*conv[k]
        M -= conv[k]
    else:
        ans += k*M
        break
        
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import time
import math

[n,m]=input().split()
a_vec=input().split()
for i in range(0,len(a_vec)):
    a_vec[i]=int(a_vec[i])
n=int(n)
m=int(m)

a_vec.sort(reverse=True)
a_vec=np.asarray(a_vec)

def count_th(a,x_th):
    cnt=0
    score=0
    min_x = max(a)
    for i in range(0,len(a)):
        tmp=a+a[i]
        tmp = tmp[tmp>=x_th]
        score=score+sum(tmp)
        cnt=cnt+len(tmp)
        if sum(tmp)==0:
            break        
        min_x = min([min(tmp), min_x])

    return(cnt,score,min_x)

def get_score(a,x):
    score=0
    for i in range(0,len(a)):
        tmp_a=a+a[i]
        
    return(score)

x_high = a_vec[0]*2
x_low  = a_vec[n-1]*2
x_tmp  = a_vec[math.floor(math.sqrt(m))]*2
coef = 0.5
check=0
check_low=0
check_high=0
min_more_cnt=n*n
min_less_cnt=n*n
while check <4:
    [tmp_cnt,tmp_score,tmp_min_x]=count_th(a_vec,x_tmp)
    cnt_diff = m-tmp_cnt

    if cnt_diff == 0:
        final_score=tmp_score
        check=5
    if tmp_cnt > m:
        if min_more_cnt >= tmp_cnt - m:
            x_low=x_tmp
            x_tmp=round(x_high*(1-coef)+x_low*coef)
            min_more_cnt = tmp_cnt - m
            min_more_cnt_score=tmp_score
         
    if tmp_cnt < m:
        if min_less_cnt >= m - tmp_cnt:
            x_high=x_tmp
            x_tmp=round(x_high*(1-coef)+x_low*coef)
            min_less_cnt = m -tmp_cnt
            min_less_cnt_score=tmp_score
    if x_high - x_low <2:
        break

if check !=5:
    final_score = min_less_cnt_score + min_less_cnt*(min_more_cnt_score-min_less_cnt_score)/(min_less_cnt+min_more_cnt)
    
print(int(final_score))

Submission status: Runtime Error

Solution code:
[n,m]=input().split()
a=input().split()
n=int(n)
m=int(m)
for i in range(0,len(a)):
    a[i]=int(a[i])
a.sort(reverse=True)
a=np.asarray(a)
x_tmp = round((a[0]*2+a[n-1]*2)*(1-(m/(n*n))))
coef=m/(n*n)

check =0
while check == 0:
    tmp=0
    for i in range(0,len(a)):
        tmp=tmp+sum(a+a[i]>x_tmp)
        
    if tmp==m:
        ans = x_tmp
        check =1
    elif tmp>m:
        x_tmp =round(x_tmp/coef)
    elif tmp<m:
        x_tmp =round(x_tmp*coef)

score=0
for i in range(0,len(a)):
    tmp=a+a[i]
    score=score+sum(tmp[tmp>x_tmp])
print(score)

Submission status: Runtime Error

Solution code:
import numpy as np
import numpy.matlib
[n,m]=input().split()
a=input().split()
n=int(n)
m=int(m)
for i in range(0,len(a)):
    a[i]=int(a[i])
a=np.sort(np.asarray(a))
a=a[::-1]

a=np.matlib.repmat(a,len(a),1)
a= a + a.transpose()
a=np.sort(a.flatten())
a=a[::-1]
print(sum(a[0:m]))

Submission status: Runtime Error

Solution code:
import numpy as np
import numpy.matlib
[n,m]=input().split()
n=int(n)
m=int(m)
a=input().split()
for i in range(0,len(a)):
    a[i]=int(a[i])

amat=np.matlib.repmat(np.asarray(a),len(a),1)
amat= amat + amat.transpose()
amat=np.matlib.repmat(np.asarray(a),len(a),1)
amat= amat + amat.transpose()
amat=np.sort(amat.flatten())
amat=amat[::-1]
print(sum(amat[0:m]))

Submission status: Runtime Error

Solution code:
import numpy as np
import numpy.matlib
[n,m]=input().split()
n=int(n)
m=int(m)
a=input().split()
#a='10 20 30 40 50 60'
for i in range(0,len(a)):
    a[i]=int(a[i])

amat=np.matlib.repmat(np.asarray(a),len(a),1)
amat= amat + amat.transpose()
amat=np.matlib.repmat(np.asarray(a),len(a),1)
amat= amat + amat.transpose()
amat=np.sort(amat.flatten())
amat=amat[::-1]
print(sum(amat[0:m]))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
from heapq import heappop, heappush

q = [(-(A[0] + A[0]), 0, 0)]
ans = []
added = {(0, 0)}
for _ in [0] * M:
    s, ai, bi = heappop(q)
    ans.append(-s)
    for da, db in ((1, 0), (0, 1)):
        aj, bj, = ai + da, bi + db
        if aj >= N or bj >= N:
            continue
        if (aj, bj) in added:
            continue
        added.add((aj, bj))
        heappush(q, (-(A[aj] + A[bj]), aj, bj))

print(sum(ans))

Submission status: Runtime Error

Solution code:
class Array
  def count
    k = Hash.new(0)
    self.each{|x| k[x] += 1 }
    return k
  end
end

N,M = gets.split(' ').map(&:to_i)
A = gets.split(' ').map(&:to_i)
a = A.count
m = M

#p a
unkey = a.keys.sort.reverse
candidates = []
# key_idx = Array.new(unkey.size,0)

(0...unkey.size).each do |i|
  candidates << [i, i, unkey[i]+unkey[i]]
end
#p unkey
#p candidates
score=0
while m > 0
  #print 'm='
  #puts m
  #p unkey[candidates[0][0]]
  x =  unkey[candidates[0][0]] + unkey[candidates[0][1]]
  #p x
  m1 = a[unkey[candidates[0][0]]] * a[unkey[candidates[0][1]]]
  if candidates[0][0] != candidates[0][1]
    m1 *= 2
  end
  combs = [m,m1].min
  #print 'combs '
  #puts combs
  # 先頭（最大値）を取ってくる


  score += candidates[0][2] * combs 
  m -= combs
  
  #print 'score '
  #puts score
  # 先頭の更新
  #print '先頭の更新 '
  #puts candidates[0][1]
  candidates[0][1] += 1
  
  if candidates[0][1] >= unkey.size
    candidates = candidates.slice(1...unkey.size)
  else
    candidates[0][2] = unkey[candidates[0][0]] + unkey[candidates[0][1]] 
    if candidates[0][2] < candidates[1][2]
      # 先頭を取り出す
      tmp = candidates[0]
      i = 1
      while tmp[2] < candidates[i][2]
        i+=1
      end  
      candidates = candidates.slice(1..i-1)+[tmp]+candidates.slice(i...unkey.size)
    end
  end
  
  #p candidates
end  

p score

Submission status: Runtime Error

Solution code:
import numpy as np
 
n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
d = 2**18
 
f = np.array([0]*d)
for i in a:
    f[i]+=1
 
tf = np.fft.fft(f)
f = np.fft.ifft(tf*tf)
f = [int(i+0.5) for i in f]
 
ans=0
for i in range(len(f)-1,0,-1):
    if f[i]<=m:
        ans+=i*f[i]
        m-=f[i]
    elif f[i]>m:
        ans+=i*m
        break
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
d = 2**15

f = np.array([0]*d)
for i in a:
    f[i]+=1

tf = np.fft.fft(f)
f = np.fft.ifft(tf*tf)
f = [int(i+0.5) for i in f]

ans=0
for i in range(len(f)-1,0,-1):
    if f[i]<=m:
        ans+=i*f[i]
        m-=f[i]
    elif f[i]>m:
        ans+=i*m
        break
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 1 << 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
A = sorted(LI(), reverse=True)
D = [0] * (10 ** 5 + 1)
acc = [0] + A
for i in range(1, n):
    acc[i + 1] += acc[i]

for i in A:
    D[i] += 1

for i in range(10 ** 5, 0, -1):
    D[i - 1] += D[i]

ok = 1
ng = max(A) * 2 + 1
while ng > ok + 1:
    mid = (ng + ok) // 2
    ret = 0
    happiness = 0
    for i in range(n):
        d = D[max(mid - A[i], 0)]
        ret += d
    if ret >= m:
        ok = mid
    else:
        ng = mid


ret2 = 0
ans = 0
for i in range(n):
    d2 = D[ng - A[i]]
    ret2 += d2
    ans = ans + d2 * A[i] + acc[d2]


ans += (m - ret2) * ok
print(ans)