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:
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
last_ok_happiness = 0
while ng > ok + 1:
    mid = (ng + ok) // 2
    ret = 0
    happiness = 0
    for i in range(n):
        d = D[max(mid - A[i], 0)]
        if ret + d >= m:
            happiness += (m - ret) * A[i] + acc[m - ret]
            ok = mid
            last_ok_happiness = happiness
            break
        else:
            ret += d
            happiness += d * A[i] + acc[d]
    else:
        ng = mid


print(last_ok_happiness)

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)]
        if ret + d >= m:
            happiness += (m - ret) * A[i] + acc[m - ret]
            ok = mid
            last_ok_happiness = happiness
            break
        else:
            ret += d
            happiness += d * A[i] + acc[d]
    else:
        ng = mid


print(last_ok_happiness)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

def isOver(A,x):
	cnt = 0
	for a in A:
		cnt += n-bisect_left(A,x-a)
	return cnt

def calOut(A,s,x):
	for a in A:
		idx = bisect_left(A,x-a)
		out += s[n]-s[idx]+a*(n-idx)
	return out - (isOver(A,n,x)-m)*x

def calX(A,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(A,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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

#累積和の下準備
a.sort()
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+a[i]

x = calX(a,m,a[0]*2,a[n-1]*2)

print(calOut(a,s,x))

Submission status: Runtime Error

Solution code:
def shake_sum(a,m):
    s = a[0] * (m+1)
    if (m-1) % 2 ==0:
        s += sum(a[1:(m-1)//2]) * 2
    else:
        s += sum(a[1:m//2]) * 2 + a[m//2]
    return s
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a = sorted(a,reverse = True)
total = 0
while m > 2*len(a)-1:
    print(a)
    total += a[0]*2*(len(a))+sum(a[1:]) *2 
    m = m-(2*len(a)-1)
    print(total)
    del a[0]
total += shake_sum(a,m)

print(total)

Submission status: Runtime Error

Solution code:
input1 = input()
input2 = input()

N,M = int(input1.split()[0]),int(input1.split()[1])

LIST_X = list(input2.split())
LIST_X.sort(reverse = True)
LIST_Y = LIST_X


SUM = 0

for i in range(M // 3):
    SUM += int(LIST_X[i]) + int(LIST_Y[i])
    SUM += int(LIST_X[i]) + int(LIST_Y[i+1])
    SUM += int(LIST_Y[i]) + int(LIST_X[i+1])

    
if M % 3 == 1:
    SUM += int(LIST_X)[M//3 * 3] + int(LIST_Y[M//3 * 3])

if M % 3 == 2:
    SUM += int(LIST_X[M//3 * 3]) + int(LIST_Y[M//3 * 3])
    SUM += int(LIST_X[M//3 * 3]) + int(LIST_Y[M//3 * 3 + 1])

print(SUM)

Submission status: Runtime Error

Solution code:
input1 = input()
input2 = input()

N,M = int(input1.split()[0]),int(input1.split()[1])

print(list(input2.split()))
LIST_X = list(input2.split())
LIST_X.sort(reverse = True)
LIST_Y = LIST_X

print(LIST_X,LIST_Y)

SUM = 0

for i in range(M // 3):
    SUM += int(LIST_X[i]) + int(LIST_Y[i])
    SUM += int(LIST_X[i]) + int(LIST_Y[i+1])
    SUM += int(LIST_Y[i]) + int(LIST_X[i+1])

    
if M % 3 == 1:
    SUM += int(LIST_X)[M//3 * 3] + int(LIST_Y[M//3 * 3])

if M % 3 == 2:
    SUM += int(LIST_X[M//3 * 3]) + int(LIST_Y[M//3 * 3])
    SUM += int(LIST_X[M//3 * 3]) + int(LIST_Y[M//3 * 3 + 1])

print(SUM)

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]

    import sys
    sys.setrecursionlimit(len(b)*len(b)*2)
    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]

    import sys
    sys.setrecursionlimit(b*b*2)
    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]

    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]
    sys.setrecursionlimit((10**5)**2+10)

    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]
    sys.setrecursionlimit((10**5)**2+10)

    res = [0]*m
    for i in b:
        for j in b:
            if res[]
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]
    sys.setrecursionlimit(b**2+10)

    res = [0]*m
    for i in b:
        for j in b:
            if res[]
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]
    sys.setrecursionlimit((m**2)*2)

    res = [0]*m
    for i in b:
        for j in b:
            if res[]
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]
    sys.setrecursionlimit(m**2)

    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加

def main():
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]

    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)
    b = a[:m]

    res = [0]*m
    for i in b:
        for j in b:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]

    res = [0]*m
    for i in a:
        for j in a:
            if min(res) < i+j:
                res[res.index(min(res))] = i+j
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)

    res = [0]*(n**2)
    cnt = 0
    for i in a:
        for j in a:
            res[cnt] = i+j
            cnt += 1
            if cnt >= len(res):
                break
        else:
            continue
        break
    ans = sorted(res, reverse=True)
    print(sum(ans[:m]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from itertools import starmap
    n, m = map(int, input().split())
    a = sorted([int(i) for i in input().split()], reverse=True)

    res = [0]*(n*n)
    cnt = 0
    for i in a:
        for j in a:
            res[cnt] = i+j
            cnt += 1
    ans = sorted(res, reverse=True)
    print(sum(ans[:m]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    if i == 30:
        x += 1
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**15:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**15:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    y = B[x]
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

Submission status: Runtime Error

Solution code:
#input
N, M = map(int, input().split())
A = (list(map(int, input().split()))

#output
import numpy as np
A = np.array(A)
A.sort()

def number_of_shake(K):
    p = np.searchsorted(A, K-A)
    return N*N - p.sum()

left = 0
right = 10**10+1
while left + 1 < right:
    mid = (left + right) // 2
    if number_of_shake(mid) >= M:
        left = mid
    else:
        right = mid

L = np.searchsorted(A, right-A)
Acum = np.zeros(N+1, np.int64)
Acum[1:] = np.cumsum(A)

shake = N*N - L.sum()
happy = (Acum[-1] - Acum[L]).sum() + (A*(N-L)).sum()
happy += (M-shake)*left

print(happy)

Submission status: Runtime Error

Solution code:
#input
N, M = map(int, input().split())
A = np.array(list(map(int, input().split())))

#output
import numpy as np
A.sort()

def number_of_shake(K):
    p = np.searchsorted(A, K-A)
    return N*N - p.sum()

left = 0
right = 10**10+1
while left + 1 < right:
    mid = (left + right) // 2
    if number_of_shake(mid) >= M:
        left = mid
    else:
        right = mid

L = np.searchsorted(A, right-A)
Acum = np.zeros(N+1, np.int64)
Acum[1:] = np.cumsum(A)

shake = N*N - L.sum()
happy = (Acum[-1] - Acum[L]).sum() + (A*(N-L)).sum()
happy += (M-shake)*left

print(happy)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = (int(w) for w in input().split()[:2])
a = np.array([int(w) for w in input().split()[:n]])
a.sort()

s = x*2
ind = [0] * n

score = 0
for i in range(m):
    k = np.argmax(s)
    ind[k] += 1
    score += s
    if k == n:
        s[k] = -1
    else:
        s[k] = a[k] + a[ind[k]]
print(score)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = (int(w) for w in input().split()[:2])
a = [int(w) for w in input().split()[:n]]
x = np.array([a])
t = (x + x.T).ravel()
t.sort()
print(sum(t[-m:]))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = [0]*(n**2)
idx = 0

for i in range(n):
	for j in range(n):
		b[i*n+j] = a[i]+a[j]

b.sort(reverse=True)

print(sum(b[:m]))

Submission status: Runtime Error

Solution code:
import itertools

n, m = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)

# aの上位m/2のみ使用
a1 = a[:(m//2)]
# aの直積
list1 = list(itertools.product(a1, repeat=2))
# list1の各タプルを合計
sum1 = sorted(list(itertools.starmap(lambda x, y: x+y, list1)), reverse=True)

val = 0
for i in range(m):
  val += sum1[i]
  
print(val)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n**2)
for i in range(n):
    for j in range(n):
        dp[i*n+j]=a[i]+a[j]
dp=sorted(dp,reverse=True)[:m]
print(sum(dp))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = np.zeros(m)
idx = 0

for i in range(n):
	for j in range(n):
		if b[idx] < a[i]+a[j]:
			b[idx] = a[i]+a[j]
			idx = np.argmin(b)

print(int(sum(b)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = [0]*m
idx = 0

for i in range(n):
	for j in range(n):
		tmp = a[i]+a[j]
		if b[idx] < tmp:
			b[idx] = tmp
			idx = b.index(min(b))

print(sum(b))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = [0]*m
tmp = 0

for i in range(n):
	for j in range(n):
		if b[tmp] < a[i]+a[j]:
			b[tmp] = a[i]+a[j]
			tmp = b.index(min(b))

print(sum(b))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = [0]*m

for i in range(n):
	for j in range(n):
		tmp = b.index(min(b))
		if b[tmp] < a[i]+a[j]:
			b[tmp] = a[i]+a[j]

print(sum(b))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n,m = (int(x) for x in input().split())
a = list(map(int, input().split()))

b = [0]*(n*n)
ans = 0

for i in range(n):
	for j in range(n):
		b[i*n+j] = a[i]+a[j]

b.sort(reverse=True)

for i in range(m):
	ans += b[i]

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
#from bisect import bisect_left
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1][:M]

ans = []
for i in range(N):
  if i <= M:
    ans = np.r_[ans,A[i] + np.array(A)]
    #ans.extend([a] + np.array(A))

ans.sort()
print(int(sum(ans[-M:])))

Submission status: Runtime Error

Solution code:
import bisect
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp
 
A.sort()
 
l = 0
r = 10**10
 
while l+1<r:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  #cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M and cnt_loop2 < M:
    break
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#print(mid, cnt_loop1, cnt_loop2)
 
S = [0] * (N+1)
for i in range(1, N+1):
  S[i] = S[i-1]+A[i-1]
#print(S[N])
 
answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

Submission status: Runtime Error

Solution code:
from itertools import accumulate

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

A.sort(reverse=True)
d = [0] * (A[0] * 2 + 1)
for i in range(N):
    d[A[i]] += 1
d = list(accumulate(d[::-1]))[::-1]
b = list(accumulate(A))

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += b[t] + A[i] * t
    m += t
print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)
d = [0] * 100001
for i in range(N):
    d[A[i]] = 1
for i in range(100000, 0, -1):
    d[i - 1] += d[i]

left = 0
right = A[0] * 2 + 1
while right - left > 1:
    mid = (left + right) // 2
    m = 0
    for i in range(N):
        m += d[max(0, mid - A[i])]
    if m >= M:
        left = mid
    else:
        right = mid

ans = 0
m = 0
for i in range(N):
    t = min(d[max(0, left - A[i])], M - m)
    ans += sum(A[:t]) + A[i] * t
    m += t
print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

root = int(sqrt(m))
happiness = sum(a[:root]) * root * 2
rest = m - root * root
half = rest // 2
happiness += a[root] * rest
happiness += sum(a[:half]) * 2
if rest % 2 == 1:
  happiness += a[half]

print(happiness)

Submission status: Runtime Error

Solution code:
from math import sqrt

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

root = int(sqrt(m))
happiness = sum(a[:root]) * root
rest = m - root * root
happiness = sum(a[:rest]) * a[root]

print(happiness)

Submission status: Runtime Error

Solution code:
from math import sart

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

root = int(sqrt(m))
happiness = sum(a[:root]) * root
rest = m - root * root
happiness = sum(a[:rest]) * a[root]

print(happiness)

Submission status: Runtime Error

Solution code:
from sys import stdin

input = stdin.buffer.readline

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

a.sort(reverse=True)

from heapq import *

q = []
heappush(q, [-(a[0] + a[0]), [0, 0]])
st = set()
ans = 0
while m:
    l, r = heappop(q)[1]
    if l == r:
        now = 1
    else:
        now = min(m, 2)
    ans += now * (a[l] + a[r])
    m -= now

    if l + 1 <= n - 1 and (min(l + 1, r), max(l + 1, r)) not in st:
        st.add((min(l + 1, r), max(l + 1, r)))
        heappush(q, [-(a[l + 1] + a[r]), [l + 1, r]])

    if r + 1 <= n - 1 and (min(l, r + 1), max(l, r + 1)) not in st:
        st.add((min(l, r + 1), max(l, r + 1)))
        heappush(q, [-(a[l] + a[r + 1]), [l, r + 1]])

    l = min(l, r) + 1
    if (l, l) not in st:
        st.add((l, l))
        heappush(q, [-(a[l] + a[l]), [l, l]])

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

max_p = max(A)

X = max_p



cnt = [0 for x in range(100001)]
hpp = [0 for x in range(100001)]


# print(A)

for i in A:
    # print(i)
    # if cnt[i] != 0:
    #     continue
    cnt[i] += 1
    hpp[i] += i
# print(cnt[:100])

for i in range(1, 100001)[::-1]:
    cnt[i - 1] += cnt[i]
    hpp[i - 1] += hpp[i]

def countpair(left, x):
    # return cnt[x - left + 1] if (x - left > 0) else N
    return cnt[x - left] if (x - left > 0) else N

def get_hpp(left, x):
    return hpp[x - left] if (x - left > 0) else hpp[0]

# print(hpp[:100])


# print(cnt[:100])

small = 0
large = max_p * 2
threshold = 0
# d_c = 0

# mems = []

while (small <= large):
    # d_c += 1
    # print(small, large)
    X = (small + large) // 2

    nums = 0
    for i in range(N):
        left = A[i]
        nums += countpair(left, X)

    if nums >= M:
        threshold = X
        small = X + 1
    else:
        large = X - 1

X = threshold

# print("X:", X)
# print("threshold:", threshold)

Y = X + 1

hpp_sum = 0
num_sum = 0

for i in range(N):
    # print("-----------")
    left = A[i]
    cnt_num = countpair(left, Y)
    num_sum += cnt_num
    # print("left:", left)
    # print("cnt_num:", cnt_num)
    hpp_sum += left * cnt_num
    # print("get_hpp:", get_hpp(left, Y))
    hpp_sum += get_hpp(left, Y)
    # print("hpp_sum:", hpp_sum)


hpp_sum += X * (M - num_sum) if (M - num_sum > 0) else 0

print(hpp_sum)


# print(out)

# for i in range(N):

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

# A = list(set(A))
# N = len(A)

max_p = max(A)
# min_p = min(A)

# sorted_A = sorted(A)

X = max_p



cnt = [0 for x in range(100001)]

hpp = [0 for x in range(100001)]


# print(A)

for i in A:
    # print(i)
    # if cnt[i] != 0:
    #     continue
    cnt[i] += 1
    hpp[i] += i
# print(cnt[:100])

for i in range(1, 100001)[::-1]:
    cnt[i - 1] += cnt[i]
    hpp[i - 1] += hpp[i]

def countpair(left, x):
    # return cnt[x - left + 1] if (x - left > 0) else N
    return cnt[x - left] if (x - left > 0) else N

def get_hpp(left, x):
    return hpp[x - left] if (x - left > 0) else hpp[0]

# print(hpp[:100])

# print(countpair(A[0], 28))

# print(cnt[:100])

small = 0
large = max_p * 2
threshold = 0
# d_c = 0

# mems = []

while (small < large):
    # d_c += 1
    # print(small, large)
    X = (small + large) // 2

    nums = 0
    for i in range(N):
        left = A[i]
        nums += countpair(left, X)

    if nums >= M:
        threshold = X
        small = X + 1    
    else:
        large = X

X = threshold

# print("X:", X)
# print("threshold:", threshold)

Y = X + 1

hpp_sum = 0
num_sum = 0

for i in range(N):
    # print("-----------")
    left = A[i]
    cnt_num = countpair(left, Y)
    num_sum += cnt_num
    # print("left:", left)
    # print("cnt_num:", cnt_num)
    hpp_sum += left * cnt_num
    # print("get_hpp:", get_hpp(left, Y))
    hpp_sum += get_hpp(left, Y)
    # print("hpp_sum:", hpp_sum)


hpp_sum += X * (M - num_sum) if (M - num_sum > 0) else 0

print(hpp_sum)


# print(out)

# for i in range(N):

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)
import numpy as np

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

a = np.tile(np.array(A), (N, 1))
m = a + a.T

print(np.sum(np.sort(m.flatten())[::-1][:M]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = np.tile(np.array(A), (N, 1))

Submission status: Runtime Error

Solution code:
input_line = input().split(' ')
numN = int(input_line[0])
numM = int(input_line[1])
power = input().split(' ')
power = [int(i) for i in power]

power.sort(reverse = True)

candidate = [0] * numM

minimum = candidate[numM - 1]

for i in power:
  for j in power:
    if minimum > i + j:
      break
    elif minimum < i + j:
      candidate[numM - 1] = i + j
      candidate.sort(reverse = True)
      minimum = candidate[numM - 1]

print(sum(candidate))

Submission status: Runtime Error

Solution code:
import numpy as np

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

#a = np.tile(np.array(A), (N, 1))
#m = a + a.T

#print(np.sum(np.sort(m.flatten())[::-1][:M]))

Submission status: Runtime Error

Solution code:
input_line = input().split(' ')
numN = int(input_line[0])
numM = int(input_line[1])
power = input().split(' ')
power = [int(i) for i in power]

power.sort(reverse = True)

candidate = [0] * numM

minimum = candidate[numM - 1]

for i in power:
  for j in power:
    if minimum > i + j:
        break
    elif minimum < i + j:
        candidate[numM - 1] = i + j
        candidate.sort(reverse = True)
        minimum = candidate[numM - 1]

print(sum(candidate))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = np.tile(np.array(A), (N, 1))
m = a + a.T

print(np.sum(np.sort(m.flatten())[::-1][:M]))

Submission status: Runtime Error

Solution code:
import sys #追加
sys.setrecursionlimit(500*500) #追加
import numpy as np

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

a = np.tile(np.array(A), (N, 1))
m = a + a.T

print(np.sum(np.sort(m.flatten())[::-1][:M]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

m = np.zeros((N, N))
for i in range(N):
  for j in range(N):
    m[i, j] = A[i] + A[j]

#print(int(np.sum(np.sort(m.flatten())[::-1][:M])))

Submission status: Runtime Error

Solution code:
import numpy as np

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

m = np.zeros((N, N))
for i in range(N):
  for j in range(N):
    m[i, j] = A[i] + A[j]

print(int(np.sum(np.sort(m.flatten())[::-1][:M])))

Submission status: Runtime Error

Solution code:
import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A,reverse=True)



happiness_list = [0]
# candidate_N_index = np.argsort(A)[int(M/2)+1]


for i in range(N):
    for j in range(M):
        power = A[i]+A[j]
        insert_index = bisect.bisect_left(happiness_list,power)
        happiness_list.insert(insert_index,power)

ans = sum(happiness_list[-M:])
print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)