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: Time Limit Exceeded

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

A.sort(reverse=True)

l=1
r=200000+1

while l+1<r:
    mid=(l+r)//2
    cnt=0
    C=0
    S=0
    for la in A:
        ll=-1
        rr=N
        while ll+1<rr:
            mi=(ll+rr)//2
            if A[mi]<=mid-la:
                rr=mi
            else:
                ll=mi
        if rr==0:
            break
        cnt+=rr
    if cnt<M:
        r=mid
    else:
        l=mid

AN=r

S=[0]*(N+1)

for i in range(N):
    S[i+1]=S[i]+A[i]

ans1=0
c=0
for la in A:
    ll = -1
    rr = N
    while ll + 1 < rr:
        mi = (ll + rr) // 2
        if A[mi] <= AN - la:
            rr = mi
        else:
            ll = mi
    if rr == 0:
        break
    c+=rr
    ans1=ans1+la*rr+S[rr]

ans=ans1+(M-c)*AN
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def judge(k, N, A):
    t = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if A[j] + i >= k:
                s = j + 1
                t += j + 1
                break
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in range(N):
        tmp += A[i]
        B.append(tmp)
    r = 0
    tot = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if i + A[j] >= X:
                tot += j + 1
                s = j + 1
                r += i * (j + 1) + B[j]
                break
    return r - (tot - M) * X
print(main())

Submission status: Time Limit Exceeded

Solution code:
import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        im = judge(m - 1, N, A)
        ip = judge(m + 1, N, A)
        if i == M:
            X = m
            break
        if im == M:
            X = m - 1
            break
        if ip == M:
            X = m + 1
            break
        if i > M:
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            if im > M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while True:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if (t >= M and t - p <= M) or t == M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while True:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while jj < 1000:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p <= M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    while True:
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if t >= M and t - p < M:
            break
        elif t > M:
            l = m + 1
        else:
            u = m - 1
        k = []
    r = 0   
    s = N
    for i in range(N):
        for j in range(s):
            if A[i] + A[j] >= m:
                r += A[i] + A[j]
            if A[i] + A[j] < m:
                s = j + 1
                break
    return r - (t - M) * m
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if p != N:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
# sys.setrecursionlimit(10000000)
INF = 1<<32


from bisect import bisect_left, bisect_right

def solve(N: int, M: int, A: "List[int]"):
        
    def binary_search(left: int, right: int):
        s = 0
        c = 0
        mi = INF

        while right-left > 1 or c < M:
            # print("test: ", left, " ", right)
            mid = (left+right)//2
            # print("mid: ", mid)
            # mid以上の価値の握手の個数を求める
            # s = []
            s = 0
            c = 0
            mi = INF
            for i in range(N):
                p = bisect_left(A, mid-A[i])
                if len(A[p:]) > 0:
                    mi = min(mi, A[i]+A[p])
                # print(A[i], A[p:], aq[N]-aq[p],  A[i]*(N-p))
                s += aq[N]-aq[p]
                s += A[i]*(N-p)
                c += N-p
                
            # mid以上の握手の個数がM以上か否か
            if c > M:
                left = mid

            else:
                right = mid
        
        s -= (c-M)*mi

        return s

    A.sort()
    aq = [0] * (N+1)
    for i in range(N):
        aq[i+1] = aq[i] + A[i]

    print(binary_search(1, A[-1]*2))
    
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A.sort(reverse=True)

l=1
r=200000+1

while l+1<r:
    mid=(l+r)//2


    cnt=0
    C=0
    S=0

    for la in A:
        for ra in A:
            if la+ra>mid:
                S+=(la+ra)
                cnt+=1
                C+=1
            else:break
    if cnt<M:
       
        r=mid
    else:
        l=mid

AN=r
ans=S+(M-C)*AN
print(ans)

Submission status: Time Limit Exceeded

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


l_power=[]
for i in range(N):
  l_power.append(l[i]*2)
  for j in range(i+1,N):
    l_power.append(l[i]+l[j])
    l_power.append(l[i]+l[j])

l_power.sort(reverse=True)
l_shake = l_power[:M]
print(sum(l_shake))

Submission status: Time Limit Exceeded

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

l_power=[]
for i in range(N):
  for j in range(N):
    l_power.append(l[i]+l[j])
l_power.sort(reverse=True)
l_shake = l_power[:M]

print(sum(l_shake))

Submission status: Time Limit Exceeded

Solution code:

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

MAX = 10**10 + 10

# Ai+Ajを列挙して大きいほうからM番目となるスコアSを求める
# その後S以上となるスコアを加算して合計値を求める

from bisect import bisect_left

def judge(x,key):
    # スコアx以上となるのがkey個以上あるか？
    
    num = 0
    
    for i in range(N):
        eidx = bisect_left(A,x-A[i])
        num += N-eidx
    
    if num >= key:
        return True
    else: 
        return False


def meguru(key):
    ok = -1
    ng = MAX
    
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if judge(mid,key):
            ok = mid
        else:
            ng = mid
    return ok


D = meguru(M)
ans = 0

ruisekiwa = [0]*(N+1)
for i in range(N):
    ruisekiwa[i+1] = ruisekiwa[i] + A[i]

num = 0

for i in range(N):
    eidx = bisect_left(A,D+0.5-A[i])
    ans += A[i] * (N-eidx)
    ans += ruisekiwa[N] - ruisekiwa[eidx]
    num += N-eidx

if num<M:
    ans += (M-num)*D

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n, m = map(int, 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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse=True)

def naive_main():
    hands = []
    for i in A:
        for j in A:
            hands.append(i + j)
    hands.sort(reverse=True)
    print(sum(hands[:m]))

naive_main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)+2

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ma=A[-1]
ng=(ma**2)*m+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ma=max(A)
ng=(ma**2)*m+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=(10**10)*m+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ng=10**15+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOk(mid,m):
    ok=mid
  else:
    ng=mid

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m=map(int,input().split())
  happ=[-int(i) for i in input().split()]
  inf=10**6
  happ.sort()
  happ.append(inf)
  from heapq import heapify,heappop,heappush
  
  
  q=[[happ[0]+happ[0],0,0],[inf]]
  heapify(q)
  ans=0
  for _ in range(m):
    ma=heappop(q)
    while q[0]==ma:
      ma=heappop(q)
    ans+=-ma[0]
    i,j=ma[1],ma[2]
    heappush(q,[happ[i+1]+happ[j],i+1,j])
    heappush(q,[happ[i]+happ[j+1],i,j+1])
  print(ans)
if  __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
class FastModuloTransform():
    def __init__(self,omega=103,n=2**18,mod=2**18*5880+1):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega,mod-2,mod)
    def _bit_reverse_(self,d):
        n = len(d)
        ns = n>>1
        nss = ns>>1
        ns1 = ns+1
        i = 0
        for j in range(0,ns,2):
            if j<i:
                d[i],d[j] = d[j],d[i]
                d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1]
            d[i+1],d[j+ns] = d[j+ns],d[i+1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d
    def _fmt_(self,A,base):
        halfpow = pow(base,self.n//2,self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base,n,self.mod)
            wk = 1
            for j in range(m):
                for i in range(j,self.n,2*m):
                    U = A[i]
                    V = (A[i+m]*wk)%self.mod
                    A[i] = (U+V)%self.mod
                    A[i+m] = (U+V*halfpow)%self.mod
                wk = (wk*w)%self.mod
            m <<= 1
        return A
    def fmt(self,f):
        A = f+[0]*(self.n-len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A,self.omega)
        return F
    def ifmt(self,F):
        A = F+[0]*(self.n-len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n,self.mod-2,self.mod)
        f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)]
        return f
    def convolute(self,f,g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s*t)%self.mod for s,t in zip(F,G)]
        h = self.ifmt(H)
        return h

omega = 159
MOD = 11280842753

N,M = map(int,input().split())
power = list(map(int,input().split()))
count = [0 for _ in range(100010)]

for p in power:
    count[p] += 1

ntt = FastModuloTransform(omega,2**18,MOD)
convoluted = ntt.convolute(count,count)

shake = 0
ans = 0

for i in range(len(convoluted))[::-1]:
    if shake + convoluted[i] <= M:
        ans += i*convoluted[i]
        shake += convoluted[i]
    else:
        ans += i*(M-shake)
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class FastModuloTransform():
    def __init__(self,omega=103,n=2**18,mod=2**18*5880+1):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega,mod-2,mod)
    def _bit_reverse_(self,d):
        n = len(d)
        ns = n>>1
        nss = ns>>1
        ns1 = ns+1
        i = 0
        for j in range(0,ns,2):
            if j<i:
                d[i],d[j] = d[j],d[i]
                d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1]
            d[i+1],d[j+ns] = d[j+ns],d[i+1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d
    def _fmt_(self,A,base):
        halfpow = pow(base,self.n//2,self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base,n,self.mod)
            wk = 1
            for j in range(m):
                for i in range(j,self.n,2*m):
                    U = A[i]
                    V = (A[i+m]*wk)%self.mod
                    A[i] = (U+V)%self.mod
                    A[i+m] = (U+V*halfpow)%self.mod
                wk = (wk*w)%self.mod
            m <<= 1
        return A
    def fmt(self,f):
        A = f+[0]*(self.n-len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A,self.omega)
        return F
    def ifmt(self,F):
        A = F+[0]*(self.n-len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n,self.mod-2,self.mod)
        f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)]
        return f
    def convolute(self,f,g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s*t)%self.mod for s,t in zip(F,G)]
        h = self.ifmt(H)
        return h

#MOD = 2**23*7*17+1 # 998244353
#MOD = 2**37*15+1 # 2061584302081
MOD = 2**31*35+1 # 75161927681

N,M = map(int,input().split())
power = list(map(int,input().split()))
count = [0 for _ in range(100010)]

for p in power:
    count[p] += 1

ntt = FastModuloTransform(78320,2**18,MOD)
convoluted = ntt.convolute(count,count)

shake = 0
ans = 0

for i in range(len(convoluted))[::-1]:
    if shake + convoluted[i] <= M:
        ans += i*convoluted[i]
        shake += convoluted[i]
    else:
        ans += i*(M-shake)
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class FastModuloTransform():
    def __init__(self,omega=103,n=2**18,mod=2**18*5880+1):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega,mod-2,mod)
    def _bit_reverse_(self,d):
        n = len(d)
        ns = n>>1
        nss = ns>>1
        ns1 = ns+1
        i = 0
        for j in range(0,ns,2):
            if j<i:
                d[i],d[j] = d[j],d[i]
                d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1]
            d[i+1],d[j+ns] = d[j+ns],d[i+1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d
    def _fmt_(self,A,base):
        halfpow = pow(base,self.n//2,self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base,n,self.mod)
            wk = 1
            for j in range(m):
                for i in range(j,self.n,2*m):
                    U = A[i]
                    V = (A[i+m]*wk)%self.mod
                    A[i] = (U+V)%self.mod
                    A[i+m] = (U+V*halfpow)%self.mod
                wk = (wk*w)%self.mod
            m <<= 1
        return A
    def fmt(self,f):
        A = f+[0]*(self.n-len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A,self.omega)
        return F
    def ifmt(self,F):
        A = F+[0]*(self.n-len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n,self.mod-2,self.mod)
        f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)]
        return f
    def convolute(self,f,g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s*t)%self.mod for s,t in zip(F,G)]
        h = self.ifmt(H)
        return h

#MOD = 2**23*7*17+1 # 998244353

MOD = 2**37*15+1 # 2061584302081

N,M = map(int,input().split())
power = list(map(int,input().split()))
count = [0 for _ in range(200010)]

for p in power:
    count[p] += 1

ntt = FastModuloTransform(1710766,2**18,MOD)
convoluted = ntt.convolute(count,count)

shake = 0
ans = 0

for i in range(len(convoluted))[::-1]:
    if shake + convoluted[i] <= M:
        ans += i*convoluted[i]
        shake += convoluted[i]
    else:
        ans += i*(M-shake)
        break

print(ans)

Submission status: Time Limit Exceeded

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

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

ans = 0

import heapq

used = [[False] * N for _ in range(N)]
ans = cnt = 0
q = [(-(A[0] + A[0]), 0, 0)]
used[0][0] = True
while cnt < M:
    penalty, x, y = heapq.heappop(q)
    ans += (A[x] + A[y])
    cnt += 1
    #
    if x + 1 < N:
        if not used[x + 1][y]:
            heapq.heappush(q, (-(A[x + 1] + A[y]), x + 1, y))
            used[x + 1][y] = True
    if y + 1 < N:
        if not used[x][y + 1]:
            heapq.heappush(q, (-(A[x] + A[y + 1]), x, y + 1))
            used[x][y + 1] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())),reverse=True)
b = []
for i in range(n):
  for j in range(min(m-i,n)):
    b.append(a[i]+a[j])
b = sorted(b,reverse=True)
print(sum(b[:m]))

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i, a in enumerate(A):
    A[i] = -a
A.sort()
h = []
"""
Contain in lst the pair (a+b, a, b) such that a+b gets smaller monotonically
At this stage we identify (a, b) with (b, a)
"""
for i in range(N):
    a = -A[i]
    for j in range(i, N):
        b = -A[j]
        heapq.heappush(h, (-a-b, a, b))

happy = 0
times = 0
while times < M:
    s, a, b = heapq.heappop(h)
    if a == b:
        happy -= s
        times += 1
    else:
        if times < M - 1:
            happy -= s * 2
            times += 2
        else:
            happy -= s
            times += 1

print(happy)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
comb_list = [ i+j for i in A for j in A]
print(sum(heapq.nlargest(M, comb_list)))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
comb_list = [ i+j for i in A for j in A]
comb_list = sorted(comb_list)
print(sum(comb_list[-M:]))

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
comb_list = []
tmp_num = 0
for i in range(N):
    for j in range(N):
        tmp_num = A[i] + A[j]
        comb_list.append(tmp_num)
comb_list = sorted(comb_list)
print(sum(comb_list[-M:]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

A.sort(reverse=True)

# (-Ax-Ay, xのidx, yのidx)
q = list()
for i, a in enumerate(A):
    heappush(q, (-a - a, i, i))

pushed = set()
ans = 0
for _ in range(M):
    hinv, x, y = heappop(q)
    ans -= hinv
    if y + 1 < N and (x, y) not in pushed:
        heappush(q, (-A[x] - A[y + 1], x, y + 1))
        heappush(q, (-A[x] - A[y + 1], x, y + 1))
    pushed.add((x, y))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
nm=input().split()
n=int(nm[0])
m=int(nm[1])
a=[int(s) for s in input().split()]
asum=[]
for i in range(n):
    asum.append(a[i]*2)
    for j in range(n-i-1):
        asum.append(a[i]+a[i+j+1])
        asum.append(a[i]+a[i+j+1])
asum.sort()
asum.reverse()
ans=0
for i in range(m):
    ans = ans + asum[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M = [int(i) for i in input().rstrip().split(' ')]
    A = [int(i) for i in input().rstrip().split(' ')]
    S = [a+b for a in A for b in A]
    S = sorted(S,reverse=True)
    #print(S)
    wel = 0
    for s in S:
        wel += s
        M -= 1
        #print(wel,s)
        if M <= 0:
            break
    print(wel)
main()