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:
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
    candi = []
    for i in range(N):
        need = base - A[i]
        c = bisect.bisect_left(A, need)
        for j in range(c,N):
            candi.append(A[i]+A[j])
    candi.sort(reverse=True)
    ans = sum(candi[:M])
    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:
n,m=map(int,input().split())
a=list(map(int,input().split()))
aij=[]
for i in range(n):
    for j in range(n):
        aij.append(a[i]+a[j])
aij.sort()
print(sum(aij[-1*m:]))

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)
	
	ans = [ 0 for _ in range(m)]
	for i in range(n):
		for j in range(i,n):
			handshake = a[i] + a[j]
			if handshake < min(ans):
				break
			else:
				ans.sort()
				if i == j:
					ans[0] = handshake
				else:
					ans[0] = handshake
					if ans[1] < handshake:
						ans[1] = handshake
					
	print(sum(ans))

if __name__ == '__main__':
	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)
	ans = []
	for i in range(n):
		for j in range(n):
			ans.append(a[i]+a[j])
	ans.sort(reverse=True)
	print(sum(ans[:m]))


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,M = (int(x) for x in input().split())
A = list(map(int,input().split()))
B = []
for i in A:
  B.append((i,i))
A = list(itertools.permutations(A,2))
A = A + B
C = []
for i in range(len(A)):
  C.append(A[i][0]+A[i][1])

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

Submission status: Time Limit Exceeded

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

# Aの累積和を求めておく
S = [0]
x = 0
for a in A:
    x += a
    S.append(x)


def lower(x):
    # A[i]<xなるiの個数
    left = -1
    right = n
    while right-left > 1:
        mid = (left+right)//2
        if A[mid] < x:
            left = mid
        else:
            right = mid
    return right


def lower_pair(x):
    # A[i]+A[j]<xなる(i,j)の個数
    cnt = 0
    for a in A:
        cnt += lower(x-a)
    return cnt


# A[i]+A[j]のm番目に大きい値を求める
# lower_pair(x)<n**2-mなる最大のxを求めればよい
left = 2*min(A)
right = 2*max(A)
while right-left > 1:
    mid = (left+right)//2
    if lower_pair(mid) < n**2-m:
        left = mid
    else:
        right = mid
x = left

# A[i]+A[j]>=xとなる(i,j)の個数とA[i]+A[j]の総和を求める
k = n**2-lower_pair(x)
s = 0
for a in A:
    cnt = lower(x-a)
    s += (n-cnt)*a+S[n]-S[cnt]

print(s-(k-m)*x)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) > k:
            left = mid
        else:
            right = mid
    ans = []
    for i in l:
        for j in l:
            if i+j >= left:
                ans.append(i+j)
    ans.sort(reverse=True)
    
    print(sum(ans[0:k]))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect

    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    def bise(x):
        count = 0

        for i in l:
            count += n-bisect.bisect_left(l,x-i)

        return count

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) > k:
            left = mid
        else:
            right = mid
    ans = []
    for i in l:
        for j in l:
            if i+j >= left:
                ans.append(i+j)
    ans.sort(reverse=True)
    
    print(sum(ans[0:k]))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
n,m = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
# naiveに考えると、max(a)から順番に握手すればいい
# 同じ握手パターンは二度使えないので、aの要素を二度まで使える、という条件の元でソートして上から使っていく
s = [i*2 for i in a]
for i in range(n):
    for j in range(i+1,n):
        s.append(a[i]+a[j])
        s.append(a[i]+a[j])
s.sort()
#print(s)
for i in range(m):
    ans += s[-1-i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 上からm番目がx
# x以上のヒトがm人以上、x+1以上のヒトがm-1人以下
# x以上のヒトがm人以上となる最大のx
from bisect import bisect_left
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = 10 ** 15

B = [0] + A[::-1]
C = list(accumulate(B))

while ng - ok > 1:
    mid = (ok + ng) // 2
    cnt = 0
    for i in range(n):
        gendo = mid - A[i]
        position = bisect_left(A, gendo)
        if position == n:
            continue
        kosuu = n - position
        cnt += kosuu
    if cnt >= m:
        ok = mid
    else:
        ng = mid
ans = 0
cnt = m
for i in range(n):
    gendo = ok - A[i]
    position = bisect_left(A, gendo)
    if position == n:
        continue
    kosuu = n - position
    ans += C[kosuu] + kosuu * A[i]
    cnt -= kosuu
ans += cnt * ok
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 isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

overEq = -1
less = 10**12
while less - overEq > 1:
    mid = (less + overEq) // 2
    if isOverEq(mid):
        overEq = mid
    else:
        less = mid

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

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

A.sort()
accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

def isOverEq(n):
    cnt = 0
    for a in A:
        cnt += N - bisect_left(A, n - a)
    return cnt >= M

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

ans = 0
cnt = 0
for a in A:
    i = bisect_left(A, overEq - a)
    ans += accA[N] - accA[i]
    ans += (N - i) * a
    cnt += N - i

ans -= max(0, cnt - M) * overEq
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    try:
        while True:
            if p<n:
                if a[i]+a[p]<=md: p+=1
                else: break
            else: break
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for i in range(n-1,-1,-1):
    try:
        while p<n:
            if a[i]+a[p]<=md: p+=1
            else: break
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[i]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0
try:
    for q in range(n-1,-1,-1):

        while p<n and a[q]+a[p]<=md:
            p+=1

        if p==n: break
        cnt+=n-p
        ans+=a[q]*(n-p)*2

except:
    b=1
    while True:
        b+=1

ans+=(m-cnt)*md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m = map(int, input().split())
a = list(map(int, input().split()))
x = []
for i in a:
	x.append(i*2)
for i in itertools.combinations(a,2):
	x.append(sum(i))
	x.append(sum(i))
x.sort(reverse=True)
print (sum(x[:m]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

MAX = max(A)

imos = [0]*(MAX*2+2)
imos[0] = N

for i in A:
  imos[i+1] -= 1
for i in range(1,len(imos)):
  imos[i] = imos[i-1]+imos[i]


def count_m(X):
  m = 0
  for i in A:
    m += imos[max(0,X-i)]
  return m

upper = MAX*2
lower = 0
X = (upper+lower)//2
m = count_m(X)

while upper != lower:
  if m > M:
    lower = (upper+lower)//2
  else:
    upper = (upper+lower-1)//2
  X = (upper+lower)//2
  m = count_m(X)

  
imos2 = [0]*(MAX*2+2)
for i in A:
  imos2[0] += i
  imos2[i+1] -= i
for i in range(1,len(imos2)):
  imos2[i] = imos2[i-1]+imos2[i]
  
ans = 0
for i in A:
  ans += i*imos[max(X-i,0)]+imos2[max(X-i,0)]
  
print(ans-(m-M)*X)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()
A.sort(reverse=True)

l = [A[i]+A[0] for i in range(N)]
n = [0]*N

MAX = A[0]*2

ans =  0
while M:
  
  for i in range(N):
    if l[i] == MAX:
      ans += MAX
      M -= 1
      t = n[i]
      n[i] += 1
      if t<N-1:
        l[i] = l[i]-A[t]+A[t+1]
      else:
        l[i] = -INF
      continue


  if max(l)<MAX:
    MAX = max(l)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()
A.sort(reverse=True)

l = [A[i]+A[0] for i in range(N)]
n = [0]*N

ans =  0
while M:
  M -= 1
  m = max(l)
  ans += m
  i = l.index(m)
  t = n[i]
  n[i] += 1
  if t<N-1:
    l[i] = l[i]-A[t]+A[t+1]
  else:
    l[i] = -INF

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import cmath
pi = cmath.pi

def expD(t):
  nexp, pexp = {}, {}
  while t != 0:
    pexp[t] = cmath.exp(2j*pi/t)
    nexp[t] = cmath.exp(-2j*pi/t)
    t //= 2
  return nexp, pexp
def powerlimit(x):
  a = 1
  while a < x:
    a *= 2
  return a

N, M = map(int, input().split())
A = list(map(int, input().split()))
m = max(A)
X = [0 for i in range(m+1)]
for i in A:
  X[i] += 1
limit = powerlimit(2*(m+1))
X = X[:] + [0 for _ in range(limit-m-1)]

nexp, pexp = expD(limit)

def fft(f, n):
  hn = n//2
  if n == 1:
    return f
  elif n == 2:
    return [f[0] + f[1], f[0] - f[1]]
  else:
    f0 = [f[2*_] for _ in range(hn)]
    f1 = [f[2*_+1] for _ in range(hn)]
    f0 = fft(f0, hn)
    f1 = fft(f1, hn)
    grow = 1
    fund = nexp[n]
    for i in range(hn):
      right = grow * f1[i]
      f[i] = f0[i] + right
      f[i+hn] = f0[i] - right
      grow *= fund
    return f
def ifft(f, n):
  hn = n//2
  if n == 1:
    return f
  elif n == 2:
    return [f[0] + f[1], f[0] - f[1]]
  else:
    f0 = [f[2*_] for _ in range(hn)]
    f1 = [f[2*_+1] for _ in range(hn)]
    f0 = ifft(f0, hn)
    f1 = ifft(f1, hn)
    grow = 1
    fund = pexp[n]
    for i in range(hn):
      right = grow * f1[i]
      f[i] = f0[i] + right
      f[i+hn] = f0[i] - right
      grow *= fund
    return f
  
F = fft(X, limit)
V = [F[i]*F[i] for i in range(limit)]
E = ifft(V, limit)
for i in range(limit):
  E[i] = int(0.5+E[i].real/limit)
cnt = 0
S = 0
point = limit - 1

while cnt < M:
  Ep = E[point]
  if Ep != 0:
    if cnt + Ep > M:
      S += (M - cnt) * point
      cnt = M
    else:
      S += point * Ep
      cnt += Ep
  point -= 1
print(S)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))

    ok = 0
    ng = 10**15
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if sum([n-bl(a, mid-a[i]) for i in range(n)]) >= m:
            ok = mid
        else:
            ng = mid

    c = -m+sum([n-bl(a, ok-a[i]) for i in range(n)])
    ans = -c*ok
    for i in range(n):
        d = bl(a, ok-a[i])
        ans += aa[n]-aa[d]+(n-d)*a[i]
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))

    ok = 0
    ng = 10**15
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        q = 0
        for i in range(n):
            q += n-bl(a, mid-a[i])
        if q >= m:
            ok = mid
        else:
            ng = mid

    b = ok
    c = -m
    for i in range(n):
        c += n-bl(a, b-a[i])
    ans = -c*b
    for i in range(n):
        d = bl(a, b-a[i])
        ans += aa[n]-aa[d]+(n-d)*a[i]
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left as bl
    from itertools import accumulate as ac

    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    aa = [0]+list(ac(a))

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

    def value(v):
        if sum([n-bl(a, v-a[i]) for i in range(n)]) >= m:
            return True
        else:
            return False

    b = b_search(0, 10**15, value)
    c = sum([n-bl(a, b-a[i]) for i in range(n)])-m
    ans = -c*b
    for i in range(n):
        d = bl(a, b-a[i])
        ans += aa[n]-aa[d]+(n-d)*a[i]
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
right = 2*10**5+5
left = 0

while right - left >1:
    mid = (right+left+1)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x >= m:
        left = mid
    else:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m = map(int,input().split())
l = list(map(int,input().split()))
l.sort()
right = 2*10**5+1
left = 0

while right - left >1:
    mid = (right+left)//2
    
    x = 0
    for i in range(n):
        a = l[i]
        index = bisect.bisect_left(l,mid-a)
        x += n-index
   
    if x >= m:
        left = mid
    else:
        right = mid
ans = []
for i in range(n):
    a = l[i]
    for j in range(n):
        if a + l[j] >= left:
            ans.append(a+l[j])
ans.sort(reverse=True)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[0]*n
C=[0]*n
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[i]=c
    d=d+c
  if d<m:
    ok=mid
    C=copy.deepcopy(B)
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  x=C[i]
  ans=ans+A[i]*x+D[x]
ans=ans+(m-sum(C))*ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
n,m=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ng=-1
ok=A[-1]*2+1
B=[0]*n
C=[0]*n
while ok-ng>1:
  mid=(ok+ng)//2
  d=0
  for i in range(n):
    c=n-bisect.bisect_right(A,mid-A[i],lo=0,hi=len(A))
    B[i]=c
    d=d+c
  if d<m:
    ok=mid
    C=copy.deepcopy(B)
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[n-i-1])
ans=0
for i in range(n):
  ans=ans+A[i]*C[i]+D[C[i]]
ans=ans+(m-sum(C))*ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
ng=-1
ok=A[0]*2+1
B=[0]*n
C=[0]*n
while ok-ng>1:
  mid=(ok+ng)//2
  c=0
  for i in range(n):
    OK=-1
    NG=n
    while NG-OK>1:
      MID=(OK+NG)//2
      if A[i]+A[MID]>=mid:
        OK=MID
      else:
        NG=MID
    B[i]=OK+1
    c=c+OK+1
  if c<m:
    ok=mid
    C=copy.deepcopy(B)
  else:
    ng=mid
D=[0]
for i in range(n):
  D.append(D[-1]+A[i])
ans=0
for i in range(n):
  ans=ans+A[i]*C[i]+D[C[i]]
ans=ans+(m-sum(C))*(ok-1)
print(ans)

Submission status: Time Limit Exceeded

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

b=sorted(b)[::-1]
print(sum(b[:m:]))

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 check(mid):
    c = 0
    for i in range(N):
        s = mid-A[i]
        c += N-bisect_left(A,s)
        if c >= M:
            return True
    return False

left = 0
right = 10**11
while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        left = mid
    else:
        right = mid
cs = [0]
for i in reversed(range(N)):
    cs.append(cs[-1]+A[i])
ans = 0
c = 0
for i in range(N):
    j = N-bisect_left(A,right-A[i])
    ans += j*A[i] + cs[j]
    c += j
ans += (M-c)*left
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def f(A):
    B=[]
    for a in range(len(A)):
        for b in range(len(A)):
            B.append(A[a]+A[b])
        B.sort(reverse=True)
    return B
input=sys.stdin.readline
n,k=map(int,input().split())
L=list(map(int,input().split()))
print(sum(f(L)[:k]))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
A = list(map(int, input().split()))
AA = []
for i in A:
    for j in A:
        AA.append(i+j)
AA.sort()
print(sum(AA[N*N-M:]))

Submission status: Time Limit Exceeded

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

def main():
    n,m=map(int,input().split())
    a=sorted(list(map(int,input().split())))
    a.reverse()
    l,r=2*a[-1],2*a[0]
    x=(l+r)//2
    while l+1<r:
        cnt=0
        for A in a:
            for B in a:
                if A+B>=x:
                    cnt+=1
                else:
                    break
        if cnt>=m:
            l=x
        else:
            r=x
        x=(l+r)//2
    s,cnt=0,0
    for A in a:
        for B in a:
            if A+B>=l:
                cnt+=1
                s+=A+B
            else:
                break
    print(s+(m-cnt)*l)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# brute force

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

happiness = []

for i in range(N):
    for j in range(N):
        happiness.append(A[i]+A[j])
    
happiness.sort(reverse=True)

print(sum(happiness[:M]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: -int(x), input().split()))
a.sort()
hq = [(a[0] + a[0], 0, 0)]
s = set()
ans = 0
for _ in range(m):
    x, i, j = heapq.heappop(hq)
    ans += x
    if i < n - 1 and (i + 1) * n + j not in s:
        heapq.heappush(hq, (a[i + 1] + a[j], i + 1, j))
        s.add((i + 1) * n + j)
    if j < n - 1 and i * n + j + 1 not in s:
        heapq.heappush(hq, (a[i] + a[j + 1], i, j + 1))
        s.add(i * n + j + 1)
print(-ans)