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=sorted(A,reverse=True)

Pair=[0 for i in range(N)]
for i in range(N-1):
    Pair[i]=A[i]+A[i+1]

ans=0
cnt=0
mode=0
Next=[]
i=0
while i<M:
    if mode==0:
        ans+=2*A[cnt]
        mode=1
        Next.append([cnt,cnt+1])
        cnt+=1
        i+=1
    else:
        Max=0
        for j in Next:
            if Max<=A[j[0]]+A[j[1]]:
                Max=A[j[0]]+A[j[1]]
                p_cnt=j
        ans+=A[p_cnt[0]]+A[p_cnt[1]]
        i+=1
        
        if i<=M-1:
            ans+=A[p_cnt[0]]+A[p_cnt[1]]
            i+=1
        Next.remove(p_cnt)
        if p_cnt[1]+1<N:
            p_cnt[1]+=1
            Next.append(p_cnt)
            
        Max=max(Max,A[p_cnt[0]]+A[p_cnt[1]])
        if Max<=A[cnt]*2 or Next==[]:
            mode=0
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, m = map(int, input().split())
a = list(map(int, input().split()))
MAX = 10 ** 5

c = Counter(a)
scores = [0] * (2 * MAX + 1)

for k1, v1 in c.items():
    for k2, v2 in c.items():
        scores[k1 + k2] += v1 * v2

ans = 0
for i, e in enumerate(scores[::-1]):
    point = 2 * MAX - i
    cnt = min(e, m)
    ans += point * cnt
    m -= cnt

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A.sort()

#
ans =[]
for i in range(N-1,-1,-1):
    ans.append(A[i] +A[i])
    for j in range(i-1,-1,-1):
        ans.extend([ A[i] +A[j],A[i] +A[j] ])
ans.sort(reverse=True)
print(sum(ans[:M]))

Submission status: Time Limit Exceeded

Solution code:
A = [1] * (1<<18)
B = [1] * (1<<18)
def convolve(a, b):
    def fft(f, w, p):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d]
                    f[j] = (x + y) % p
                    f[j+d] = u * (x - y) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f, w, p):
        d = 1
        while d < n:
            v = pow(w, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    x = f[j]
                    y = f[j+d] * u
                    f[j] = (x + y) % p
                    f[j+d] = (x - y) % p
                u = u * v % p
            d *= 2
 
    p, g = (81 << 27) + 1, 7
    n0, n1 = len(a), len(b)
    n = 1 << ((max(n0, n1) - 1).bit_length() + 1)
    a = a[:] + [0] * (n-n0)
    b = b[:] + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    fft(a, w, p)
    fft(b, w, p)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a, pow(w, p - 2, p), p)
    invn = pow(n, p - 2, p)
    for i in range(n0 + n1 - 1):
        a[i] = a[i] * invn % p
    return a

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.array(input().split(), np.int32)
f = np.bincount(A)

fft_len = len(f) * 2 - 1
fft = np.fft.rfft
ifft = np.fft.irfft
Ff = fft(f, fft_len)
G = np.rint(ifft(Ff * Ff, fft_len)).astype(np.int64)

ans = 0
for i, x in enumerate(G[::-1], 1):
    if x == 0:
        continue
    ans += (fft_len - i) * min(M, x)
    M -= x
    if M <= 0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
A = np.array(input().split(), np.int64)
MAX = 2 * max(A)
prev = np.zeros(MAX + 1, np.int64)
dp = np.zeros(MAX + 1, np.int64)

for a in A:
    prev[a] += 1
for a in A:
    dp[a:] += prev[:-a]

ans = 0
for i, x in enumerate(dp[::-1]):
    if x == 0:
        continue
    # print(MAX - i, x)
    ans += (MAX - i) * min(M, x)
    M -= x
    if M <= 0:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
n,m = map(int,input().split())
a = list(map(int,input().split()))

b = [0]*(n+1)
a.sort()
for i in range(n):
  b[i+1] = b[i]+a[i]

def is_ok(arg):
    c = 0
    f = False
    for i in a:
      if c >= m:
        break
      c += (n-bisect_left(a,arg-i))
    if c >= m:
      f = True
    return f

def bisect_ok(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

x = bisect_ok(2*a[-1]*m+1,1)
ans = 0
cnt = 0
for i in a:
  ind = n-bisect_left(a,x-i)
  cnt += ind
  ans += i*ind+(b[-1]-b[n-ind])
if cnt > m:
  ans -= x*(cnt-m)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
import bisect
# 解説の二分探索
# あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。ちょうどM個以上になるXを探す
l,r=0,a[-1]*2
while r-l>1:
  x=(l+r)//2
  cnt=0
  for ai in a:
    cnt+=n-bisect.bisect_left(a,x-ai)
  # x以上がm個以上ある->xを増加
  [l,r]=[x,r] if cnt>=m else [l,x]
x=(l+r)//2
ans=[]
for ai in a:
  bi=bisect.bisect_left(a,x-ai)
  ans.extend([aj+ai for aj in a[bi:]])
ans.sort()
print(sum(ans[-m:]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ruiseki = list(accumulate(A[::-1]))

# 自分以上の数の個数がM個以上になる値のうち最大のもの
ok = 0
ng = 10 ** 15
while ok + 1 < ng:
    mid = (ok + ng) // 2
    cnt = 0
    ans = 0
    for a in A:
        x = bisect.bisect_left(A, mid - a)
        cnt += N - x
        if N - x >= 1:
            ans += ruiseki[N - x - 1] + (N - x) * a
    if cnt >= M:
        ok = mid
    else:
        ng = mid
# okで終わってる場合はcntがM個以上の場合があるから過分を引く
# ngで終わってる場合は残りM-cnt個のokを足す
print(ans + ok * (M - cnt))

Submission status: Time Limit Exceeded

Solution code:
import heapq

n,m = map(int, raw_input().split(' '))
elems = map(int, raw_input().split(' '))
elems.sort()

heap = [(-elems[i] - elems[-1], i,len(elems) - 1) for i in range(len(elems))]
heapq.heapify(heap)
cumul = 0

while(m):
	m -=1
	v, i, j = heapq.heappop(heap)
	cumul -= v
	if j -1 >=0: heapq.heappush(heap, (-elems[i] - elems[j-1], i, j - 1))
print cumul

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, raw_input().split(' '))
elems = map(int, raw_input().split(' '))

cs = [elems[i] + elems[j] for i in range(len(elems)) for j in range(len(elems))]
cs.sort(key = lambda x:-x)
print sum(cs[:m] or [0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, l, sums):
    ss = 0
    mins = []
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ss += sums[n] - sums[idx]
        ss += (n - idx) * a
        if l <= 0:
            continue
        while idx < n and (len(mins) < l or mins[0] < -(a + A[idx])):
            if len(mins) >= l:
                heapq.heappop(mins)
            heapq.heappush(mins, -(a + A[idx]))
            idx += 1
    #print(mins)
    ret = ss + sum(mins)
    return ret

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = sum(A)
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    cnt = _count(A, N, l)
    ret = _sum(A, N, l, cnt - M, sums)
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print(i, j)
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print(j, i)
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    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, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, M):
    vals = []
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        for i in range(idx, n):
            vals.append(a + A[i])
    vals.sort(reverse=True)
    #print(vals)
    ret = sum(vals[:M])
    return ret

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = sum(A)
    ret = 0
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    ret = _sum(A, N, l, M)
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print(i, j)
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print(j, i)
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    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:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    summary = [a[i] + a[j] for i in range(n) for j in range(n)]
    summary.sort(reverse=True)
    ans = 0
    for i in range(m):
        ans += summary[i]
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    summary = [a[i] + a[j] for i in range(n) for j in range(n)]
    summary.sort(reverse=True)
    print(sum(summary[0:m]))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
a = list(map(int,input().split()))
list.sort(a,reverse=True)
ans = 0

kouho = [[0,0]]
for i in range(m):
    max = 0
    m0 = -1
    m1 = -1
    for j in kouho:
        if a[j[0]]+a[j[1]] > max:
            max = a[j[0]]+a[j[1]]
            m0 = j[0]
            m1 = j[1]
    ans += max
    kouho.remove([m0,m1])
    if m0 < n-1 and (not [m0+1,m1] in kouho):
        kouho.append([m0+1,m1])
    if m1 < n-1 and (not [m0,m1+1] in kouho):
        kouho.append([m0,m1+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

if __name__ == '__main__':
    def check(mid):
        count = 0
        for i in range(n):
            position = bisect.bisect_left(a, (mid - a[i]))
            count += (n - position)
        return count < m


    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    # 左手でa[i]の手を握るとする
    # a[i]を持っているときに和がx未満になるときの右手の数字はx - a[i]未満の数字である
    # lower_bound
    # この値をNから引くことで和がx以上になるペアの個数がわかる
    # この値の合計がM未満になればそこが最大の幸福度である

    # 要するに、M個のペアを作るためには最大いくらの和を採用できるかを二分探索する

    ng = 0
    ok = 10 ** 5 * (n + 1)

    while 1 < abs(ok - ng):
        # mid -> boundとなる和。これより大きい和をもつペアをM個作れるかを判定する
        mid = (ok + ng) // 2
        c = check(mid)
        # ペアの個数がmより小さい場合は、okの範囲を下げる
        if c:
            ok = mid
        # そうでない場合はまだ余裕があるので、ngをあげる
        else:
            ng = mid

    # ここが終了した時点でngにはm個以上のペアを作るための最大のboundが入っている

    # upper_boundで左手にa[i]がある場合のng - a[i]の数を判定する
    # ansに求めた数 * a[i] + 右手に持つ幸福度の総和を足す
    # mから求めた数を引く

    ans = 0
    sum_array = [0] * (n + 1)
    # 累積和で高速化をする
    # (x + a[i]) + (x + a[i + 1) + (x + a[i + 2]).....
    #   -> (x * 個数) * (a[i] + a[i + 1] + a[i + 2])

    for i in range(n):
        sum_array[i + 1] = sum_array[i] + a[i]
    for i in range(n):
        position = bisect.bisect_right(a, ng - a[i])
        ans += (n - position) * a[i] + sum_array[n] - sum_array[position]
        m -= (n - position)

    ans += ng * m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**18
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E
import heapq
import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

# A1に対してをいれる
h = []
for i in range(N):
    heapq.heappush(h, (-(A[i]+A[0]), i, 0))

ans = 0
for i in range(M):
    val, idx, idx2 = heapq.heappop(h)
    ans -= val
    if idx2+1 < N:
        heapq.heappush(h, (-(A[idx]+A[idx2 + 1]), idx, idx2 + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def resolve():
    n, m = map(int, input().split())
    l = list(map(int, input().split()))
    n = max(l)
    qrtn = 2 ** int(np.ceil(np.log2(2 * n - 1)))
    a = np.zeros(qrtn)
    for i in l:
        a[i - 1] += 1
    b = a.copy()
    c = np.fft.ifft(np.fft.fft(a) * np.fft.fft(b))
    d = [0] + [int(x) for x in np.real(c[:2 * n - 1] + 0.5)]
    ans = 0
    i = n * 2 - 1
    while m > 0:
        if d[i]:
            ans += i + 1
            m -= 1
            d[i] -= 1
        else:
            i -= 1
    print(ans)


resolve()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=map(int,input().split())
A=sorted(map(int,input().split()))
left,right=-1,10**20
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)
    cnt+=N-b
    ans+=r[N]-r[b]
print(ans-D*(cnt-M))

Submission status: Time Limit Exceeded

Solution code:
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=map(int,input().split())
A=sorted(map(int,input().split()))
left,right=-1,10**20
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)
    cnt+=N-b
    ans+=r[N]-r[b]
print(ans-D*(cnt-M))

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
l = []
for i in range(n):
  for j in range(i,n):
    l.append(-(a[i]+a[j]))
    if i != j :
      l.append(-(a[i]+a[j]))
heapq.heapify(l)
sum = 0
for k in range(m):
    sum += heapq.heappop(l)*(-1)
    
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for i in range(n):
    k=A[i]
    for j in range(n):
        B.append(k+A[j])
s=0
B.sort(reverse=True)
print(sum(B[0:m]))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for v1,v2 in itertools.product(A,repeat=2):
    B.append(v1+v2) 
s=0
B.sort(reverse=True)
print(sum(B[0:m]))

Submission status: Time Limit Exceeded

Solution code:
import bisect


def solve(mid):
    cnt = 0
    r = n
    for i in range(n):
        l = bisect.bisect_left(a, mid - a[i])
        cnt += (r - l)
    return cnt >= m
    

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

ok = 0
ng = 10 ** 18
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + a[i]

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.bisect_left(a, ok - a[i])
    cnt += (r - l)
    ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[x+y for x in A for y in A]
s=0
B.sort(reverse=True)
print(sum(B[0:m]))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=[x+y for x in A for y in A]
s=0
for i in range(m):
    k=B.index(max(B))
    s=s+B[k]
    B[k]=0
print(s)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_right

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

    def calc(x):
        tmp = 0
        for a in A:
            tmp += N - bisect_right(A, x - a - 0.5)
        return tmp

    l = 0
    r = 3 * 10 ** 5
    while r - l > 1:
        mid = (l + r) // 2
        if calc(mid) >= M:
            l = mid
        else:
            r = mid

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

    ans = 0
    for a in A:
        tmp = bisect_right(A, r - a - 0.5)
        M -= (N - tmp)
        ans += a * (N - tmp) + (B[-1] - B[tmp])

    ans += M * l
    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

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

def calc(x):
    tmp = 0
    for a in A:
        tmp += N - bisect_right(A, x - a - 0.5)
    return tmp

l = 0
r = 3 * 10 ** 5
while r - l > 1:
    mid = (l + r) // 2
    if calc(mid) >= M:
        l = mid
    else:
        r = mid

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

ans = 0
for a in A:
    tmp = bisect_right(A, r - a - 0.5)
    M -= (N - tmp)
    ans += a * (N - tmp) + (B[-1] - B[tmp])

ans += M * l
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

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

def calc(m): #m以下の組が何通りあるかを数える
    count = 0 #組数を数える
    for a in A:
        b = m - a #b以上のは含める
        count += N - bisect_right(A, b - 0.5)
    return count

l = 0 
r = 3 * 10 ** 5

while r - l > 1:
    mid = (l + r) // 2
    if calc(mid) >= M: #合計mid以上の組と手を繋ぐとしたとき、とM回以上握手できる
        l = mid
    else:
        r = mid

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

# print(B)
flag = False
for i in range(mid + 3, -1, -1):
    if calc(i) < M:
        flag = False
    else: #初めて手をにぎる回数がM回を下回ったとき
        break

i += 1 #合計この値までは全て使う、残り回数を調整
ans = 0
for a in A:
    b = i - a
    tmp = bisect_right(A, b - 0.5)
    M -= (N - tmp) #使った数
    ans += a * (N - tmp) + (B[-1] - B[tmp])

ans += M * (i - 1)
print (ans)

Submission status: Time Limit Exceeded

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

score=[]
for i in range(n):
    for j in range(n):
        score.append(a[i]+a[j])
score.sort()
sum = 0
for i in range(1,m+1):
    sum+=score[-i]
print(sum)

Submission status: Time Limit Exceeded

Solution code:
#python3
INF = int(1e9)

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()
    s = [0]
    for i in range(n):
        s.append(s[i]+a[i])
    #Xより大きい要素の数を数える
    def counter(x):
        count = 0
        for i in range(n):
            l = -1
            r = n
            while r-l>1:
                mid = (l+r)//2
                if a[i] + a[mid] > x:
                    r = mid
                else:
                    l = mid
            count += n-r
        return count
    
    #Xより大きい要素数がm個未満であるXのうち最大のものを探す
    l = 0 
    r = INF
    while r-l>1:
        mid = (l+r)//2
        if counter(mid) < m:
            r = mid
        else:
            l = mid

    #lより大きい要素の総和を求める 
    def sigma(x):
        cnt = 0
        sgm = 0
        for i in range(n):
            l = -1
            r = n
            while r-l >1:
                mid = (l+r)//2
                if a[i]+a[mid]>x:
                    r = mid
                else:
                    l = mid
            cnt += n-r
            sgm += a[i] * (n-r) + (s[n]-s[r])
        return (sgm, cnt)

    sgm, cnt = sigma(l)
    ans = sgm+(m-cnt)*r
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
# E - Handshake

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

A.sort(reverse=True)

S = []
S.append(A[0])
for i in range(N-1):
    S.append(S[i]+A[i+1])
S.append(0)

# 幸福度がX以上となる握手がM以上になることを考える
# つまり、幸福度がXより大きい(X+1以上)の握手と
# 幸福度がXの握手を足すとM以上

def CheckHappy(x):
    X = list(map(lambda y: x - y, A))
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], S[l])
            happy += A[i]*(l+1)+S[l]
    #print('cnt, happy', cnt, happy)
    return cnt, happy

def isGreaterThanM(x):
    X = list(map(lambda y: x - y, A))
    #print('X',X)
    cnt = 0
    for i in range(N):
        l = -1
        r = N
        #print('l, r', l, r)
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        #print('cnt',cnt)
        if cnt >= M:
            return True
    return False


# 2分探索
left = min(A)*2-1
right = max(A)*2+1

while left+1 < right:
    mid = (left+right)//2
    if isGreaterThanM(mid):
        left = mid
    else:
        right = mid

#print('left, right', left, right)

tmp, ans = CheckHappy(right)
ans += (M-tmp)*left
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E - Handshake

import numpy as np

N, M = map(int, input().split())
A = list(int(x) for x in input().split())
A.sort(reverse=True)
A = np.array(A)
Acsum = np.zeros(N+1,dtype=np.int64)
Acsum[0:N] = np.cumsum(A)

left = min(A)*2-1
right = max(A)*2+1

def Check(x):
    X = x-A
    cnt = 0
    happy = 0
    for i in range(N):
        l = -1
        r = N
        while l+1 < r:
            m = (l+r)//2
            if A[m] >= X[i]:
                l = m
            else:
                r = m 
        cnt += l+1
        if l>=0:
            #print(A[i], Acsum[l])
            happy += A[i]*(l+1)+Acsum[l]
    return cnt, happy
    
# 2分探索
while left+1 < right:
    mid = (left+right)//2
    if Check(mid)[0] >= M:
        left = mid
    else:
        right = mid

tmp, ans = Check(right)
ans += (M-tmp)*left
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    ma = max(A)
    l = 0; r = ma*2+1
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for a in A:
            need = now-a
            if need>ma:
                continue
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    for a in A:
        need = base - a
        c = bisect.bisect_left(A, need+1)
        ans += a*(N-c) + sum(A[c:])
        cnt += (N-c)
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    l = 0; r = max(A)*2+1
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for i in range(N):
            need = now-A[i]
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    for i in range(N):
        need = base - A[i]
        c = bisect.bisect_left(A, need+1)
        for j in range(c,N):
            ans += A[i]+A[j]
            cnt += 1
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    A.sort()
    l = 0; r = 10**6
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for i in range(N):
            need = now-A[i]
            c = bisect.bisect_left(A,need)
            cnt += N-c
        if cnt>=M:
            l = now
        else:
            r = now
    base = l
    cnt = 0
    ans = 0
    for i in range(N):
        need = base - A[i]
        c = bisect.bisect_left(A, need+1)
        for j in range(c,N):
            ans += A[i]+A[j]
            cnt += 1
    if cnt<M:
        ans += base*(M-cnt)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""