Problem:


Score : 500 points

Problem Statement

Takahashi has come to a party as a special guest.
There are N ordinary guests at the party. The i-th ordinary guest has a power of A_i.

Takahashi has decided to perform M handshakes to increase the happiness of the party (let the current happiness be 0).
A handshake will be performed as follows:

Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).

Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).

What is the maximum possible happiness after M handshakes?

Constraints

1 \leq N \leq 10^5

1 \leq M \leq N^2

1 \leq A_i \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the maximum possible happiness after M handshakes.

Sample Input 1

5 3
10 14 19 34 33

Sample Output 1

202

Let us say that Takahashi performs the following handshakes:

In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.

In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.

In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.

Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202.

We cannot achieve the happiness of 203 or greater, so the answer is 202.

Sample Input 2

9 14
1 3 5 110 24 21 34 5 3

Sample Output 2

1837

Sample Input 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

Sample Output 3

8128170



Sample input:
5 3
10 14 19 34 33


Sample output:
202

Submission status: Runtime Error

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

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())

B = []
for a in A:
    B.extend(A + a)
B.sort(reverse=True)

answer = B[:M].sum()
print(answer)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    a = LI()
    a.sort()
    l = 0
    r = 2*a[-1]
    while r-l > 1:
        x = (l+r) >> 1
        s = 0
        for i in a:
            j = bisect.bisect_left(a,x-i)
            s += n-j
        if s <= m:
            r = x
        else:
            l = x
    s = [0]*n
    s[-1] = a[-1]
    for i in range(n-1)[::-1]:
        s[i] = s[i+1]+a[i]
    res = m
    ans = 0
    for i in a:
        j = bisect.bisect_left(a,r-i)
        if j < n:
            ans += min(res,(n-j))*i
            if res < n-j:
                j = n-res
            ans += s[j]
            res -= n-j
            if res < 0:
                res = 0
    print(ans+res*l)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# coding: utf-8

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
A.sort(reverse=True)

count = 0
kouhuku = 0
h1, h2 = 0, 0
th = 1
while True:
    print(N, h1, h2)
    kouhuku += A[h1] + A[h2]
    count += 1
    if count < M and h1 != h2:
        kouhuku += A[h1] + A[h2]
        count += 1

    if count >= M:
        break

    h2 += 1
    if h2 >= N or A[h1] + A[h2] < A[h1 + th] * 2:
        h1 += 1
        h2 = h1

print(kouhuku)

Submission status: Runtime Error

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, M = map(int, input().split())
A = list(map(int, input().split()))
#A.sort(reverse=True)

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

B.sort(reverse=True)

print(sum(B[:M]))

Submission status: Runtime Error

Solution code:
t = int(input())
for i in range(t):
    #Nc2
    n= int(input());
    print(int((n*(n-1))/2))

Submission status: Runtime Error

Solution code:
def main():
    n,m = map(int,input().split())
    a = sorted(list(map(int,input().split())))
    ans = 0
    sa = sum(a)-a[-1]
    while True:
        if m == 0:
            break
        r = a[-1]
        if m >= 2*n-1:
            ans += sa*2+r*2*n
        elif m == 1:
            ans += r*2
            break
        else:
            ans += r*2
            del a[-1]
            m -= 1
            for i in range(m//2):
                ans += a.pop(-1)*2+r*2
            if m%2 == 1:
                ans += a.pop(-1)+r
            break
        m -= 2*n-1
        n -= 1
        del a[-1]
        sa -= a[-1]
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def mh_push(h, v):
    heapq.heappush(h, -v)

def mh_pop(h):
    return -heapq.heappop(h)

@mt
def slv(N, M, A):
    A.sort(reverse=True)

    h = []
    i = 0
    for j in range(i, N):
        mh_push(h, A[i]+A[j])
        if i != j:
            mh_push(h, A[i]+A[j])
    c = 0
    if i < N-1:
        v = A[i+1] + A[i+1]
    else:
        v = -1
    ans = 0
    while c != M:
        cand = mh_pop(h)
        if cand >= v:
            ans += cand
            c += 1
        else:
            mh_push(h, cand)
            i += 1
            for j in range(i, N):
                mh_push(h, A[i]+A[j])
                if i != j:
                    mh_push(h, A[i]+A[j])
            if i < N-1:
                v = A[i+1] + A[i+1]
            else:
                v = -1


    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M,A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

A.sort()
mem = dict()

ng, ok = 0, A[-1] * 2 + 1
while ok - ng > 1 :
  m = (ok + ng) // 2
  c = 0
  for i in range(N) :
    c += N - bisect_left(A, m - A[i])
  mem[m] = c
  if c <= M :
    ok = m
  else :
    ng = m
  
S = [A[0]]
for i in range(1, N) :
  S.append(S[-1] + A[i])
S.append(0)

all = sum(A)
ret = 0
for i in range(N) :
  ret += all - S[bisect_left(A, m - A[i])-1]
  ret += A[i] * (N - bisect_left(A, m - A[i]))
ret += (M - mem[ok]) * (ok - 1)
print(ret)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def mh_push(h, v):
    heapq.heappush(h, -v)

def mh_pop(h):
    return -heapq.heappop(h)

@mt
def slv(N, M, A):
    A.sort(reverse=True)

    h = []
    i = 0
    for j in range(i, N):
        mh_push(h, A[i]+A[j])
        if i != j:
            mh_push(h, A[i]+A[j])
    c = 0
    v = A[i+1] + A[i+1]
    ans = 0
    while c != M:
        cand = mh_pop(h)
        if cand >= v:
            ans += cand
            c += 1
        else:
            mh_push(h, cand)
            i += 1
            for j in range(i, N):
                mh_push(h, A[i]+A[j])
                if i != j:
                    mh_push(h, A[i]+A[j])
            if i < N-1:
                v = A[i+1] + A[i+1]
            else:
                v = -1


    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M,A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = np.array(a).reshape(-1, 1)
mat = a + a.T
print(np.sum(np.sort(mat.flatten())[::-1][:m]))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
ax = []

for i in range(n):
    ax.append([a[i]+a[j] for j in range(n)])

print(ax)

nt = m
score = 0

for i in range(n):
    for j in range(n):
        print(score)
        if (nt == 0):
            break
        elif (i == j):
            score += ax[i][j]
            nt -= 1
        elif(ax[i+1][i+1] < ax[i][j]):
            score += ax[i][j]
            nt -= 1
            if (nt > 0):
                score += ax[i][j]
                nt -= 1
        else:
            score += ax[i + 1][i + 1]
            nt -= 1
print(score)

Submission status: Runtime Error

Solution code:
import heapq


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

idx_dict = {}
for i in range(n):
    idx_dict[i] = i+1

ans = [A[i]+A[i] for i in range(n)]
candidates = [[-(A[i]+A[i+1]), i] for i in range(n-1)]
heapq.heapify(candidates)

for i in range(m//2):
    num, idx = heapq.heappop(candidates)
    ans.append(-num)
    ans.append(-num)
    idx_dict[idx] += 1
    new_pair = idx_dict[idx]
    if new_pair >= n:
        continue
    candidate = A[idx] + A[new_pair]
    heapq.heappush(candidates, [-candidate, idx])

ans.sort(reverse=True)
print(sum(ans[:m]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

def mh_push(h, v):
    heapq.heappush(h, -v)

def mh_pop(h):
    return -heapq.heappop(h)

@mt
def slv(N, M, A):
    A.sort(reverse=True)

    h = []
    i = 0
    for j in range(i, N):
        mh_push(h, A[i]+A[j])
        if i != j:
            mh_push(h, A[i]+A[j])
    c = 0
    v = A[i+1] * A[i+1]
    ans = 0
    while c != M:
        cand = mh_pop(h)
        if cand >= v:
            ans += cand
            c += 1
        else:
            mh_push(h, cand)
            i += 1
            for j in range(i, N):
                mh_push(h, A[i]+A[j])
                if i != j:
                    mh_push(h, A[i]+A[j])
            if i < N-1:
                v = A[i+1] * A[i+1]
            else:
                v = -1


    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    print(slv(N, M,A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq

n, m = map(int, input().split())
a = [int(x) for x in input().split()]
a = list(set(a))
a.sort(reverse=True)
key = []
judge = [[False]*n for i in range(n)]

heapq.heappush(key, [-(a[0]+a[0]), 0, 0])
judge[0][0] = True

ans = 0
for i in range(m):
    p = heapq.heappop(key)
    p1, p2, p3 = p[0], p[1], p[2]
    ans += (-p1)
    if p2 < n-1 and judge[p2+1][p3] == False:
        heapq.heappush(key, [-(a[p2+1]+a[p3]), p2+1, p3])
        judge[p2+1][p3] = True
    if p3 < n-1 and judge[p2][p3+1] == False:
        heapq.heappush(key, [-(a[p2]+a[p3+1]), p2, p3+1])
        judge[p2][p3+1] = True

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.read
N, M, *A = map(int, read().split())
A = np.array(A, np.int64)

a = A[None, :] + A[:, None]
a = a.flatten()

a.sort()
print(a[-M:].sum())