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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

"""
N, M = getNM()
weight = []
key = []
for _ in range(M):
    a, b = getNM()
    weight.append(a)
    c = getList()
    key.append(c)

dp = [float('inf')] * (1 << N)
dp[0] = 0
for i in range(M):
    bit = 0
    for item in key[i]:
        bit |= (1 << (item - 1))
    for j in range(1 << N):
        dp[j | bit] = min(dp[j | bit], dp[j] + weight[i])

print(dp)
"""

"""
ARC028 B-特別賞
N, K = getNM()
A = getList()
young = [0] * N
# i番目に若い人の順位はyoung[i]位
for i in range(N):
    young[A[i] - 1] = i

A = [-i for i in A]
# Aの前からK個のリストを作る
prized = []
for i in range(K):
    prized.append(A[i])
heapq.heapify(prized)

# K個数字があるうちの最大値（K番目の数字）を取ってくる
now = heapq.heappop(prized)
print(young[-now - 1] + 1)

for i in range(K, N):
    # もし現在のK番目の数字より小さい数字がきたら
    if A[i] > now:
        # prizedリストに混ぜて（計K個入っている）
        heapq.heappush(prized, A[i])
        # 再びK個数字があるうちの最大値（K番目の数字）を取ってくる
        now = heapq.heappop(prized)
        print(young[-now - 1] + 1)
    # もし現在のK番目の数字より小さい数字がきたら捨てる
    else:
        print(young[-now - 1] + 1)
"""

"""
ABC062 D - 3N Numbers
N = getN()
A = getList()

# 前から計算
fore = A[:N]
# 後ろから計算
back = A[2 * N:]
back = [-i for i in back]
for_sum = sum(fore)
back_sum = sum(back)
heapq.heapify(fore)
heapq.heapify(back)

fore_list = []
back_list = []
for i in range(N):
    fore_list.append(for_sum)
    back_list.append(back_sum)
    in_fore = A[N + i]
    heapq.heappush(fore, in_fore)
    out_fore = heapq.heappop(fore)
    for_sum += in_fore - out_fore

    in_back = (-1) * A[-N - i - 1]
    heapq.heappush(back, in_back)
    out_back = heapq.heappop(back)
    back_sum += in_back - out_back

fore_list.append(for_sum)
back_list.append(back_sum)

ans = -float('inf')
for i in range(N + 1):
    opt = fore_list[i] + back_list[N - i]
    ans = max(ans, opt)
print(ans)
"""

"""
# ABC123 D - Cake 123
X, Y, Z, K = getNM()
A = sorted([-i for i in getList()])
B = sorted([-i for i in getList()])
C = sorted([-i for i in getList()])

pos = []
heapify(pos)
dict = defaultdict(int)
u = (A[0] + B[0] + C[0], 0, 0, 0)
heappush(pos, u)
dict[u] = 1

for i in range(K):
    p, i, j, l = heappop(pos)
    print(-p)
    # 取り出すごとにA, B, Cについての次の値をpush
    if i + 1 < X:
        opt_a = (A[i + 1] + B[j] + C[l], i + 1, j, l)
        if dict[opt_a] == 0:
            heappush(pos, opt_a)
            dict[opt_a] = 1
    if j + 1 < Y:
        opt_b = (A[i] + B[j + 1] + C[l], i, j + 1, l)
        if dict[opt_b] == 0:
            heappush(pos, opt_b)
            dict[opt_b] = 1
    if l + 1 < Z:
        opt_c = (A[i] + B[j] + C[l + 1], i, j, l + 1)
        if dict[opt_c] == 0:
            heappush(pos, opt_c)
            dict[opt_c] = 1
"""
# ABC149 E - Handshake
# Mがクソデカイので使用不可
# 二分探索使ってね
N, M = getNM()
A = sorted([-i for i in getList()])

pos = []
heapify(pos)
dict = defaultdict(int)
u = (A[0] + A[0], 0, 0)
heappush(pos, u)
dict[u] = 1

ans = 0
# 大きい値M番目まで全て求まる
for i in range(M):
    p, i, j = heappop(pos)
    ans += -p
    if i + 1 < N:
        opt_a = (A[i + 1] + A[j], i + 1, j)
        if dict[opt_a] == 0:
            heappush(pos, opt_a)
            dict[opt_a] = 1
    if j + 1 < N:
        opt_b = (A[i] + A[j + 1], i, j + 1)
        if dict[opt_b] == 0:
            heappush(pos, opt_b)
            dict[opt_b] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

"""
N, M = getNM()
weight = []
key = []
for _ in range(M):
    a, b = getNM()
    weight.append(a)
    c = getList()
    key.append(c)

dp = [float('inf')] * (1 << N)
dp[0] = 0
for i in range(M):
    bit = 0
    for item in key[i]:
        bit |= (1 << (item - 1))
    for j in range(1 << N):
        dp[j | bit] = min(dp[j | bit], dp[j] + weight[i])

print(dp)
"""

"""
ARC028 B-特別賞
N, K = getNM()
A = getList()
young = [0] * N
# i番目に若い人の順位はyoung[i]位
for i in range(N):
    young[A[i] - 1] = i

A = [-i for i in A]
# Aの前からK個のリストを作る
prized = []
for i in range(K):
    prized.append(A[i])
heapq.heapify(prized)

# K個数字があるうちの最大値（K番目の数字）を取ってくる
now = heapq.heappop(prized)
print(young[-now - 1] + 1)

for i in range(K, N):
    # もし現在のK番目の数字より小さい数字がきたら
    if A[i] > now:
        # prizedリストに混ぜて（計K個入っている）
        heapq.heappush(prized, A[i])
        # 再びK個数字があるうちの最大値（K番目の数字）を取ってくる
        now = heapq.heappop(prized)
        print(young[-now - 1] + 1)
    # もし現在のK番目の数字より小さい数字がきたら捨てる
    else:
        print(young[-now - 1] + 1)
"""

"""
ABC062 D - 3N Numbers
N = getN()
A = getList()

# 前から計算
fore = A[:N]
# 後ろから計算
back = A[2 * N:]
back = [-i for i in back]
for_sum = sum(fore)
back_sum = sum(back)
heapq.heapify(fore)
heapq.heapify(back)

fore_list = []
back_list = []
for i in range(N):
    fore_list.append(for_sum)
    back_list.append(back_sum)
    in_fore = A[N + i]
    heapq.heappush(fore, in_fore)
    out_fore = heapq.heappop(fore)
    for_sum += in_fore - out_fore

    in_back = (-1) * A[-N - i - 1]
    heapq.heappush(back, in_back)
    out_back = heapq.heappop(back)
    back_sum += in_back - out_back

fore_list.append(for_sum)
back_list.append(back_sum)

ans = -float('inf')
for i in range(N + 1):
    opt = fore_list[i] + back_list[N - i]
    ans = max(ans, opt)
print(ans)
"""

"""
# ABC123 D - Cake 123
X, Y, Z, K = getNM()
A = sorted([-i for i in getList()])
B = sorted([-i for i in getList()])
C = sorted([-i for i in getList()])

pos = []
heapify(pos)
dict = defaultdict(int)
u = (A[0] + B[0] + C[0], 0, 0, 0)
heappush(pos, u)
dict[u] = 1

for i in range(K):
    p, i, j, l = heappop(pos)
    print(-p)
    # 取り出すごとにA, B, Cについての次の値をpush
    if i + 1 < X:
        opt_a = (A[i + 1] + B[j] + C[l], i + 1, j, l)
        if dict[opt_a] == 0:
            heappush(pos, opt_a)
            dict[opt_a] = 1
    if j + 1 < Y:
        opt_b = (A[i] + B[j + 1] + C[l], i, j + 1, l)
        if dict[opt_b] == 0:
            heappush(pos, opt_b)
            dict[opt_b] = 1
    if l + 1 < Z:
        opt_c = (A[i] + B[j] + C[l + 1], i, j, l + 1)
        if dict[opt_c] == 0:
            heappush(pos, opt_c)
            dict[opt_c] = 1
"""

N, M = getNM()
A = sorted([-i for i in getList()])

pos = []
heapify(pos)
dict = defaultdict(int)
u = (A[0] + A[0], 0, 0)
heappush(pos, u)
dict[u] = 1

ans = 0
# 大きい値M番目まで全て求まる
for i in range(M):
    p, i, j = heappop(pos)
    ans += -p
    if i + 1 < N:
        opt_a = (A[i + 1] + A[j], i + 1, j)
        if dict[opt_a] == 0:
            heappush(pos, opt_a)
            dict[opt_a] = 1
    if j + 1 < N:
        opt_b = (A[i] + A[j + 1], i, j + 1)
        if dict[opt_b] == 0:
            heappush(pos, opt_b)
            dict[opt_b] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Polynomial:
    def __init__(self,dim=0,const=1):
        self.coefficient = np.zeros(dim+1, np.int64)
        self.coefficient[dim] = const

    def __add__(self,other): # +
        f,g = self.coefficient, other.coefficient
        if len(f) > len(g): f,g = g,f

        h = Polynomial(dim=len(g)-1,const=0)
        h.coefficient[len(f):] += g[len(f):]
        h.coefficient[:len(f)] += f + g[:len(f)]
        return h
    
    def __iadd__(self,other): # +=
        h = self.__add__(other)
        self.coefficient = h.coefficient
        return self

    def __mul__(self,other): # *
        f = self.coefficient
        g = other.coefficient
        h = Polynomial()
        h.coefficient = self.fft(f,g)[:len(f)+len(g)-1]
        return h
    
    def __len__(self):
        return len(self.coefficient)

    def __getitem__(self,key):
        return self.coefficient[key]

    def get_coefficient(self,x):
        return self.coefficient[x]


    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)



def main():
    N,M=mi()
    A=list(mi())
    
    mx = 2*10**5+10
    f = Polynomial(dim=0,const=0)
    for a in A:
        f += Polynomial(dim=a)
            
    g = f * f
    ans = 0
    handshake = M
    for x in range(len(g)-1,1,-1):
        count = g[x]
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

    def get_coefficient(self,dim):
        return self.f[dim]

    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)

    def convolve(self,g):
        h = self.fft(self.f,g)[:len(self.f) + len(g) - 1]
        self.f = h
    


def main():
    N,M=mi()
    A=list(mi())
    
    mx = 2*10**5+10
    F = PolySolver(mx,init_val=0)
    for a in A:
        F.add(Polynomial(dim=a).values,MOD=mx)
    
    g = F.f
    F.convolve(g)

    ans = 0
    handshake = M
    for x in range(mx-1,1,-1):
        count = F.get_coefficient(x)
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

    def get_coefficient(self,dim):
        return self.f[dim]

    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)

    def convolve(self,g):
        h = self.fft(self.f,g)[:len(self.f) + len(g) - 1]
        self.f = h
    


def main():
    N,M=mi()
    A=list(mi())
    
    mx = 2*10**5+10
    F = PolySolver(mx,init_val=0)
    G = PolySolver(mx,init_val=0)
    for a in A:
        F.add(Polynomial(dim=a).values,MOD=mx)
        G.add(Polynomial(dim=a).values,MOD=mx)
    
    F.convolve(G.f)

    ans = 0
    handshake = M
    for x in range(mx-1,1,-1):
        count = F.get_coefficient(x)
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

    def get_coefficient(self,dim):
        return self.f[dim]

    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)

    def convolve(self,g):
        h = self.fft(self.f,g)[:len(self.f) + len(g) - 1]
        self.f = h
    


def main():
    N,M=mi()
    A=list(mi())
    
    mx = 2*10**5+10
    F = PolySolver(mx,init_val=0)
    for a in A:
        F.add(Polynomial(dim=a).values,MOD=mx)
    
    g = F.f.copy()
    F.convolve(g)

    ans = 0
    handshake = M
    for x in range(mx-1,1,-1):
        count = F.get_coefficient(x)
        if count <= 0: continue

        if count > handshake:
            ans += handshake * x
        else:
            ans += count * x
 
        handshake = max(handshake-count,0)
        if handshake == 0:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect_left
from itertools import accumulate

def resolve():
    def getCount(x):
        cnt = 0
        for a in A:
            # X未満の個数
            idx = bisect_left(A, x - a)
            # X以上の個数
            cnt += N - idx
        # X以上を使う！と決めた時、M個以上になるか
        return cnt >= M

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

    ng = 10 ** 18
    ok = 0
    # X以上を使う！と決めるとX以上の個数が自明にわかる。
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if getCount(mid):
            ok = mid
        else:
            ng = mid

    # M個以上あることがわかれば、Mよりも余分な数(同じ値が複数ある場合)
    # はすべてXである事がわかるため、差分だけ引けば良い。
    B = [0] + list(accumulate(A))
    ans = 0
    cnt = 0
    for i in range(N):
        idx = bisect_left(A, ok - A[i])
        ans += B[N] - B[idx] + A[i] * (N - idx)
        cnt += N - idx

    rest = (cnt - M) * ok
    print(ans - rest)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as BL 
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()

#border以上の幸福度を返す握手の組の数が、M以上であるか
def isok(border):
  res=0
  for i in range(N):
    res+=N-BL(A,border-A[i])
  return res>=M
    

ok=0
ng=A[-1]*2+1
mid=(ok+ng)//2

#幸福度h以上の握手がM組以上存在するような最大のhを探す
while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if isok(mid):
    ok=mid
  else:
    ng=mid
  
ans=0
shake_c=0
for i in range(N):
  goodshake=N-BL(A,ok-A[i])
  shake_c+=goodshake
  for j in range(goodshake):
    ans+=A[i]+A[-1-j]
    
ans-=(shake_c-M)*ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
from heapq import heappush, heappop, heapify

def bisect(ng, ok, judge, eps=1):
    while abs(ng-ok) > eps:
        m = (ng+ok)//2
        if judge(m):
            ok = m
        else:
            ng = m
    return ok

N,M = map(int,input().split())
A = sorted(map(int,input().split()))
acc = [0]+list(accumulate(A))

def judge(p):
    j = N
    cnt = 0
    for al in A:
        while j > 0 and al+A[j-1] >= p:
            j -= 1
        cnt += N-j
    return cnt <= M

p = bisect(0, A[-1]*2+1, judge)

j = N
cnt = 0
res = 0
q = []
for al in A:
    while j > 0 and al+A[j-1] >= p:
        j -= 1
    cnt += N-j
    res += (N-j)*al + acc[-1]-acc[j]
    if j > 0:
        q.append((-(al+A[j-1]),al,j-1))

heapify(q)
for _ in range(M-cnt):
    p,al,j = heappop(q)
    res -= p
    if j > 0:
        heappush(q, (-(al+A[j-1]),al,j-1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = list(map(int, input().split(' ')))
if n == 1:
    print(ttt[0] * 2)
    exit()

d = {}
for i in range(min(n, 15000)):
    for j in range(i, min(n, 15000)):  # 1e5 ** 2... TLE
        d[ttt[i] + ttt[j]] = d.get(ttt[i] + ttt[j], 0) + (2 if i != j else 1)

ans = 0
for i in range(2000000, -1, -1):
    t = d.get(i, 0)
    ans += i * min(t, k)
    k = max(k-t, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = list(map(int, input().split(' ')))
if n == 1:
    print(ttt[0] * 2)
    exit()

d = {}
for i in range(min(n, 25000)):
    for j in range(i, min(n, 25000)):  # 1e5 ** 2... TLE
        d[ttt[i] + ttt[j]] = d.get(ttt[i] + ttt[j], 0) + (2 if i != j else 1)

ans = 0
for i in range(2000000, -1, -1):
    t = d.get(i, 0)
    ans += i * min(t, k)
    k = max(k-t, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = list(map(int, input().split(' ')))
if n == 1:
    print(ttt[0] * 2)
    exit()

d = {}
for i in range(min(n, 25000)):
    for j in range(i, min(n, 25000)):  # 1e5 ** 2... TLE
        d[ttt[i] + ttt[j]] = d.get(ttt[i] + ttt[j], 0) + (2 if i != j else 1)

ans = 0
for i in range(2000000, -1, -1):
    t = d.get(i, 0)
    ans += i * min(t, k)
    k = max(k-t, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = list(map(int, input().split(' ')))
if n == 1:
    print(ttt[0] * 2)
    exit()

d = {}
for i in range(min(n, 30000)):
    for j in range(i, min(n, 30000)):  # 1e5 ** 2... TLE
        d[ttt[i] + ttt[j]] = d.get(ttt[i] + ttt[j], 0) + (2 if i != j else 1)

ans = 0
for i in range(2000000, -1, -1):
    t = d.get(i, 0)
    ans += i * min(t, k)
    k = max(k-t, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = list(map(int, input().split(' ')))
if n == 1:
    print(ttt[0] * 2)
    exit()

d = {}
for i in range(n):
    for j in range(i, n):  # 1e5 ** 2... TLE
        d[ttt[i] + ttt[j]] = d.get(ttt[i] + ttt[j], 0) + (2 if i != j else 1)

ans = 0
for i in range(2000000, -1, -1):
    t = d.get(i, 0)
    ans += i * min(t, k)
    k = max(k-t, 0)
print(ans)

Submission status: Time Limit Exceeded

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

N,M = map(int,readline().split())
A = sorted(list(map(int,readline().split())))
allA = sum(A)
sumA = [0] + A.copy()
for i in range(1,len(sumA)):
  sumA[i] += sumA[i - 1]

# 左手34,33,19,14,10
# 右手34,33,19,14,10
# X以上の握手をできる組だけ採用する
# 例：50以上の握手をできるのは、
# 左手34に対しては34,33,19
# 右手33に対しては34,33,19
# この合計がM回を越えると採用できない。
# M回を下回る場合は、すべての握手の合計で最大値を更新

ok = -1
ng = 10 ** 5 * 2 + 1

import bisect
def isOk(x):
  # x以上の握手だけ採用するとき、採用できる場合に全体の合計点はいくつになるか
  cnt = 0
  for left in A:
    right = x - left
    ind = bisect.bisect_left(A, right)
    #print("N - ind",N - ind)
    cnt += N - ind
  #print("x",x,"cnt",cnt)
  if cnt >= M:
    return True
  else:
    return False

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

# ok以上の握手だけ許容する場合の点数を算出
ans = []
#print("A",A)
for left in A:
  right = ok - left
  ind = bisect.bisect_left(A, right)
  #print("ok",ok,"left",left,"right",right,"ind",ind)
  for r in range(ind, len(A)):
    #print("left",left,"A[r]",A[r])
    ans.append(A[r] + left)

ans = sorted(ans, reverse = True)
#print(ans)
print(sum(ans[:M]))

Submission status: Time Limit Exceeded

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

N,M = map(int,readline().split())
A = sorted(list(map(int,readline().split())))
allA = sum(A)
sumA = [0] + A.copy()
for i in range(1,len(sumA)):
  sumA[i] += sumA[i - 1]

# 左手34,33,19,14,10
# 右手34,33,19,14,10
# X以上の握手をできる組だけ採用する
# 例：50以上の握手をできるのは、
# 左手34に対しては34,33,19
# 右手33に対しては34,33,19
# この合計がM回を越えると採用できない。
# M回を下回る場合は、すべての握手の合計で最大値を更新

ok = -1
ng = 200

import bisect
def isOk(x):
  # x以上の握手だけ採用するとき、採用できる場合に全体の合計点はいくつになるか
  cnt = 0
  for left in A:
    right = x - left
    ind = bisect.bisect_left(A, right)
    #print("N - ind",N - ind)
    cnt += N - ind
  #print("x",x,"cnt",cnt)
  if cnt >= M:
    return True
  else:
    return False

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

# ok以上の握手だけ許容する場合の点数を算出
ans = []
#print("A",A)
for left in A:
  right = ok - left
  ind = bisect.bisect_left(A, right)
  #print("ok",ok,"left",left,"right",right,"ind",ind)
  for r in range(ind, len(A)):
    #print("left",left,"A[r]",A[r])
    ans.append(A[r] + left)

ans = sorted(ans, reverse = True)
#print(ans)
print(sum(ans[:M]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.asarray(a_list)
l = np.array([])
for i in a:
    l = np.append(l, i+a)
l.sort()
print(int(np.sum(l[-M:])))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

happy.sort(reverse=True)
nxt = [0]*N
ab = [0]*N
ans = 0
for k in range(M):
    for n in range(N):
        if nxt[n] < N:
            newx = happy[n] + happy[nxt[n]]
            heapq.heappush(ab, -newx)
            nxt[n] += 1
    ans -= ab[0]
    heapq.heappop(ab)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    def S():
        return sys.stdin.readline().rstrip()

    N, M = map(int, S().split())
    A = LI()
    A.sort()

    from bisect import bisect_left

    low = 2
    high = 2 * A[-1] + 1

    while low + 1 < high:
        mid = (low + high) // 2
        if sum(N - bisect_left([A[i] + A[j] for j in range(N)], mid) for i in range(N)) >= M:
            low = mid
        else:
            high = mid

    a = low  # a以上のA[i]+A[j]がM個以上となる最大のa

    from itertools import accumulate

    B = [0] + list(accumulate(A))

    r = 0
    ans = 0
    for i in range(N):  # a+1以上のA[i]+A[j]を足し合わせていく
        b = bisect_left([A[i] + A[j] for j in range(N)], a + 1)
        r += N - b
        ans += B[N] - B[b]
        ans += A[i] * (N - b)

    ans += (M - r) * a  # A[i]+A[j] == a となるものを足し合わせる

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
l=[]
l = [[i, j] for i in a for j in a]
l_1 = [sum(i) for i in l]
#print(l_1, len(l_1))
print(sum(sorted(l_1)[len(l_1)-M:]))
#for b in a:
#    for c in a:
#        l.append(b + c)

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
l=[]
for b in a:
    for c in a:
        l.append(b + c)
print(sum(sorted(l)[len(l)-M:]))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for k, A in enumerate(As, start=1):
            i = bisect_left(As, x-A)
            num += N-i
            if num >= M:
                return True
            elif num + (N-k)*N < M:
                return False
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 10**10+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()