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 numpy as np

N ,M= map(int,input().split())
l=list(map(int,input().split()))
n0 = 2**int(np.ceil(np.log2(2*(max(l)+1) - 1)))

A = np.zeros(n0)
#B=np.zeros(n0)
#l=list(map(int,input().split()))

for i in range(N):
    A[l[i]]+=1
   # B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(A) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*(max(l)+1)- 1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Submission status: Runtime Error

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

k = 0
if m <= n*(n+1)//2:
  while (k+1)*(k+2)//2 <= m:
    k += 1
  for i in range(k):
    happy += a[i]*(2*(k-i))
  if k < n:
    b=m-k*(k+1)//2
    c=[0]*(k+1)
    for i in range(k+1):
      c[i]=a[i]+a[k+1-i]
    c.sort(reverse=True)
    happy += sum(c[:b])
else:
  while (k+1)*(k+2)//2 <= n**2 - m:
    k += 1
  happy = 2*n*sum(a)
  for i in range(k):
    happy -= a[n-1-i]*2*(k-i)
  b=m-k*(k+1)//2
  c=[0]*(k+1)
  for i in range(k+1):
    c[i]=a[i]+a[k+1-i]
  c.sort()
  happy -= sum(c[:b])

print(happy)

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	N := readInt()
	M := readInt()
	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = readInt()
	}

	sort.Sort(sort.Reverse(sort.IntSlice(A)))
	U := A[0] * 2
	L := A[N-1] * 2

	// cgs[i] は パワーがi以上のゲストの数
	cgs := make([]int, U+1)
	for _, a := range A {
		cgs[a]++
	}
	for i := U; i > 0; i-- {
		cgs[i-1] += cgs[i]
	}

	isOk := func(n int) bool {
		m := 0
		for _, a := range A {
			m += cgs[max(n-a, 0)]
		}
		return m >= M
	}

	ok := L
	ng := U + 1
	for ng-ok != 1 {
		m := ok + (ng-ok)/2
		if isOk(m) {
			ok = m
		} else {
			ng = m
		}
	}

	// cps[i] は A[0]～A[i] の累積和
	cps := make([]int, N)
	cps[0] = A[0]
	for i := 1; i < N; i++ {
		cps[i] = A[i] + cps[i-1]
	}

	result := 0
	for _, a := range A {
		guests := cgs[max(ok-a, 0)]
		if guests != 0 {
			result += a*guests + cps[guests-1]
			M -= guests
		}
	}
	result += ok * M
	fmt.Println(result)
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
alist = [0]*(n**2)

for i in range(n):
  for j in range(n):
    alist[i*n+j] = a[i]+a[j]
alist.sort(reverse=True)

print(sum(alist[:m]))

Submission status: Runtime Error

Solution code:
import numpy as np

N ,M= map(int,input().split())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B=np.zeros(n0)
l=list(map(int,input().split()))

for i in range(N):
    A[i]=l[i]
    B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*N - 1] + 0.5):
    #ans+=int(ci)*j
    q.append([int(ci),j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N ,M= map(int,input().split())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B=np.zeros(n0)
l=list(map(int,input().split()))

for i in range(N):
    A[i]=l[i]
    B[i]=l[i]

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
q=[]
for ci in np.real(C[:2*N - 1] + 0.5):
    #ans+=int(ci)*j
    q.append([ci,j])
    j+=1
q.reverse()
z=0
j=0
while z<M:
    ans+=q[j][0]*q[j][1]
    j+=1
    z+=q[j][0]
ans-=(z-M)*q[j][1]
print(ans)

Submission status: Runtime Error

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

for i in range(n):
  for j in range(n):
    alist[i*n+j] = a[i]+a[j]
alist.sort(reverse=True)

print(sum(alist[:m]))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
n0 = 2**int(np.ceil(np.log2(2*N - 1)))

A = np.zeros(n0)
B = np.zeros(n0)
for i in range(N):
    A[i], B[i] = map(int, input().split())

C = np.fft.ifft( np.fft.fft(A)*np.fft.fft(B) )
ans=0
j=1
for ci in np.real(C[:2*N - 1] + 0.5):
    ans+=int(ci)*j
    j+=1
print(ans)

Submission status: Runtime Error

Solution code:
import math
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
sq = int(math.sqrt(m))
rest = m - sq*sq
ans = sum(a[0:sq]) * sq
ans += a[sq]*rest
ans += sum(a[0:rest//2]) * 2
ans += a[rest//2] * (rest%2)
print(ans)

Submission status: Runtime Error

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

A = [int(tmp[i]) for i in range(N)]


score = [None]*(N*N)
for i in range(N):
    for j in range(N):
        score[i*N+j] = A[i] + A[j]
score.sort()
sum = 0
for i in range(M):
    sum += score[N*N-1-i]
print(sum)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import sys
import bisect

input = sys.stdin.readline

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

a.sort(reverse = True)

li = [0] * (10**5+1)

for i in a:
    li[i] += 1

acm = list(accumulate(li))
acm_a = list(accumulate(a))

l = 0
r = 2 * 10 ** 5

while l <= r:
    mid = (l + r) // 2
    count = 0
    for i in a:
        if mid - i >= 0:
            count += n - acm[mid-i]
        else:
            count += n
    if count >= m:
        l = mid + 1
    else:
        r = mid - 1

sum_idx = 0
ans = 0
b = a[::-1]
for left in a:
    right_min = l - left
    idx = bisect.bisect_left(b,right_min)
    if n - idx > 0:
        sum_idx += n - idx
        ans += left * (n - idx) + acm_a[n - idx - 1]

ans -= l * (sum_idx - m)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

n0 = 2**int(np.ceil(np.log2(2*Amax - 1)))#Amax+1以上となる最小の2のべき乗数

Afre=np.zeros(n0).astype(int)#パワーの頻度(1~Amax+1)
for i in range(N):
    Afre[A[i]]+=1

#astype(int)は切り捨てなので，rintで四捨五入してから．
S = np.rint(np.fft.irfft(np.fft.rfft(Afre)*np.fft.rfft(Afre))).astype(int)
Scum =S.cumsum()#累積和
bd = N*N-M#上からM個を取り出したい
i=np.searchsorted(Scum,bd)#価値iを生み出せる組みがM個以上ある
#価値iが生み出せる選び方の余分なものを引きたい
remove=((Scum[-1]-Scum[i])-M)*i

ans=0
for j in range(i+1,n0):
    ans+=S[j]*j
print(ans-remove)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1][:M]

def ins(ans,a):
  index = bl(ans,a)
  return np.insert(ans,index,a)[:M]

m = int(min(M,N))
ans = np.zeros(1, np.int64)
#ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.append(ans,[[a] + A for a in A])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[-1])))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = list(map(int,input().split()))
B = []
C = []
A.sort(reverse=True)
for i in range(N):
  B.append(A[i]*2)
for i in range(N-1):
  for j in range(i+1,N):
    C.append(A[i]+A[j])
    C.append(A[i]+A[j])
cnt1 = 0
cnt2 = 0
ans = 0
while(True):
  if (B[cnt1] >= C[cnt2]) and (cnt1 < len(B)):
    ans += B[cnt1]
    cnt1 += 1
    if cnt1+cnt2 == M:
      break
  elif (B[cnt1] < C[cnt2]) and (cnt2 < len(C)):
    ans += C[cnt2]
    cnt2 += 1
    if cnt1+cnt2 == M:
      break
  elif cnt2 == len(C):
    ans += B[cnt1]
    cnt1 += 1
    if cnt1+cnt2 == M:
      break
  else:
    ans += C[cnt2]
    cnt2 += 1
    if cnt1+cnt2 == M:
      break
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,M = list(map(int, input().split()))
        A = np.asarray(list(map(int, input().split())))
        
    else:
        A = 6
        for i in range(0,A,4):
            print(i)
    
    S = np.zeros((N*N))
    
    for n in range(N):
        for m in range(N):
            S[n+m*N] = A[n] + A[m]


    print(int(np.sum(np.sort(S)[::-1][0:M])))
    



if __name__ =='__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
A = A[:int(np.sqrt(M)+1)]
n = len(A)
m = int(min(M,n))
ans = np.zeros(1)
ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
A = A[:int(np.sqrt(M)+1)]

m = int(min(M,len(A)))
ans = np.zeros(1)
ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
A = A[:int(np.sqrt(M)+2)]

m = int(min(M,N))
ans = np.zeros(1)
ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
A = A[:int(np.sqrt(M)+1)]

m = int(min(M,N))
ans = np.zeros(1)
ans = np.append(ans,[[a] + A for n,a in enumerate(A) if n<=m])
ans = np.sort(ans)[::-1][:M]
print(int(sum(ans[:M])))

Submission status: Runtime Error

Solution code:
import sys

nm = list(input().split(" "))
N = int(nm[0])
M = int(nm[1])
A = list(input().split(" "))
A = list(map(lambda x:int(x),A))
A.sort()
A.reverse()

ans = 0

start ,counter  = 0 , 0
flag1 = 0 # every step first time
flag2 = 0 # repete
flag3 = 0 # next step
for i in range(0,M):
    if flag1 == 0:
        ans += int(A[start]) + int(A[counter])
        counter += 1
        flag1 = 1
    elif flag2 == 0:
        ans += int(A[start]) + int(A[counter])
        flag2 = 1
    else:
        ans += int(A[start]) + int(A[counter])
        flag2 = 0
        if flag3 == 0:
            counter += 1
            if counter == N-1:
                flag3 = 1
        else:
            flag1 = 0
            flag3 = 0
            start += 1
            counter = start

print(ans)

Submission status: Runtime Error

Solution code:
def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return 0
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
# nmx(x) : x以上のペアが何通りあるか
r = bsearch(-M, 1, mx*2, nmx)
r += 1
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
rr += (r-1)*(M-c)
print(rr)

Submission status: Runtime Error

Solution code:

def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
# nmx(x) : x以上のペアが何通りあるか
r = bsearch(-M, 1, mx*2, nmx)
r += 1
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
rr += (r-1)*(M-c)
print(rr)

Submission status: Runtime Error

Solution code:
def nmx(x):
    r = 0
    for a in As:
        r += d2[max(0, x-a)]
    return -r
def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())))
mn, mx = As[0], As[-1]

j = 0
n = N
d2 = []
for i in range(mx*2):
    while True:
        if j>=N:
            break
        if i <= As[j]:
            break
        j += 1
        n -= 1
    d2.append(n)
# d2[i] : i以上のaがいくつあるか
r = bsearch(-M, 1, 10**7, nmx)
from itertools import accumulate
aas = list(accumulate([0]+As[::-1]))
rr = 0
c = 0
for a in As[::-1]:
    if c+d2[max(0, r-a)] > M:
        rr += a*(M-c) + aas[M-c]
        break
    else:
        rr += a*d2[max(0, r-a)] + aas[d2[max(0, r-a)]]
    c += d2[max(0, r-a)]
print(rr)

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 f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

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

    i = b.bisect_left(M, 1, N)
    if f(i) != M:
        i -= 1
    l = f(i)

    ans = 0
    for j in range(i):
        ans += A[j] * 2
        ans += A[j] * (i-1)

    rem = M - l
    print(i, l, rem)
    j = 0
    while rem != 0:
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        ans += A[j] + A[i]
        rem -= 1
        if rem == 0:
            break
        j += 1


    return ans

import numpy as np
def slv2(N, M, A):
    C = Counter(A)
    B = [C[i] for i in range(2**18)]
    D = np.fft.rfft(B)
    D *= D
    E = list(np.fft.irfft(D).real)
    ans = 0
    c = 0
    i = 2**18 - 1
    while c != M:
        n = int(E[i])
        if n != 0:
            if c + n > M:
                n = M-c
            c += n
            ans += i * n
        i -= 1
        assert i != -1

    return ans

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

    # N = 10**5
    # M = random.randint(1, N**2)
    # A = [random.randint(1, 10**5) for _ in range(N)]
    # print(slv(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from queue import PriorityQueue

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

pq = PriorityQueue()
pq.put(-(arr[0] + arr[0]))
for i in range(1, n):
    pq.put(-(arr[0] + arr[i]))
    pq.put(-(arr[0] + arr[i]))

idx = 1
res = 0
while m:
    v = -pq.get()
    if v < 2 * arr[idx]:
        pq.put(-v)
        pq.put(-(arr[idx] + arr[idx]))
        for jdx in range(idx+1, n):
            pq.put(-(arr[idx] + arr[jdx]))
            pq.put(-(arr[idx] + arr[jdx]))
        idx += 1
    else:
        res += v
        m -= 1

print(res)

Submission status: Runtime Error

Solution code:
# input
s1 = str(input())
s2 = str(input())
s1s = s1.split(' ')
N = int(s1s[0])
M = int(s1s[1])
guests = list(map(int, s2.split(' ')))

# preprocess (counting)
maximum = guests[0]
minimum = guests[0]
for guest in guests:
  if maximum < guest:
    maximum = guest
  if minimum > guest:
    minimum = guest

COUNT_SUM = [0] * (maximum + 1)
for guest in guests:
  COUNT_SUM[guest] += 1 # count

TOTAL_SUM = [] # cumulative sum
for idx in range(1, len(COUNT_SUM)): # COUNT_SUM[i]: number of guests with value less than i 
  # first use cumulative sum
  if COUNT_SUM[idx] > 0:
    for _ in range(COUNT_SUM[idx]):
      if len(TOTAL_SUM) > 0:
        TOTAL_SUM.append(idx + TOTAL_SUM[-1])
      else:
        TOTAL_SUM.append(idx)
        
  # second use cumulative count
  COUNT_SUM[idx] = COUNT_SUM[idx] + COUNT_SUM[idx - 1]

def count_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    total += candidate
  return total

def sum_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    subsum = TOTAL_SUM[N - 1] - TOTAL_SUM[N - candidate - 1] if candidate < N else TOTAL_SUM[N - 1]
    subsum += guest * candidate
    total += subsum
  return total

right = maximum * 2
left = minimum * 2
temp = {}
while left < right:
  target_x = int((right + left) / 2)
  target_num = count_more_than(target_x)
  temp[target_x] = target_num
  if target_num > M:
    left = target_x + 1# increase left
  elif target_num < M:
    right = target_x - 1# decrease right
  else:
    break # found

target_sum = sum_more_than(target_x)
#if target_num == M:
#  pass
# elif target_num < M:
#   more_target_num = -1
#   for idx in range(target_x - 1, minimum * 2, - 1):
#       if idx not in temp:
#         temp[idx] = count_more_than(idx)
#       if temp[idx] > M:
#         more_target_num = temp[idx]
#         break
#   more_target_sum = sum_more_than(idx)
#   diff = int((more_target_sum - target_sum) / (more_target_num - target_num))
#   target_sum += diff * (M - target_num)
# elif target_num > M:
#   less_target_num = -1
#   for idx in range(target_x + 1, maximum * 2):
#       if idx not in temp:
#         temp[idx] = count_more_than(idx)
#       if temp[idx] < M:
#         less_target_num = temp[idx]
#         break
#   less_target_sum = sum_more_than(idx)
#   diff = int((target_sum - less_target_sum) / (target_num - less_target_num))
#   target_sum -= diff * (target_num - M)
#print("%d,%d,%d" % (target_x, target_num, target_sum))
print(target_sum)

Submission status: Runtime Error

Solution code:
# input
s1 = str(input())
s2 = str(input())
s1s = s1.split(' ')
N = int(s1s[0])
M = int(s1s[1])
guests = list(map(int, s2.split(' ')))

# preprocess (counting)
maximum = guests[0]
minimum = guests[0]
for guest in guests:
  if maximum < guest:
    maximum = guest
  if minimum > guest:
    minimum = guest

COUNT_SUM = [0] * (maximum + 1)
for guest in guests:
  COUNT_SUM[guest] += 1 # count

TOTAL_SUM = [] # cumulative sum
for idx in range(1, len(COUNT_SUM)): # COUNT_SUM[i]: number of guests with value less than i 
  # first use cumulative sum
  if COUNT_SUM[idx] > 0:
    for _ in range(COUNT_SUM[idx]):
      if len(TOTAL_SUM) > 0:
        TOTAL_SUM.append(idx + TOTAL_SUM[-1])
      else:
        TOTAL_SUM.append(idx)
        
  # second use cumulative count
  COUNT_SUM[idx] = COUNT_SUM[idx] + COUNT_SUM[idx - 1]

def count_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    total += candidate
  return total

def sum_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    subsum = TOTAL_SUM[N - 1] - TOTAL_SUM[N - candidate - 1] if candidate < N else TOTAL_SUM[N - 1]
    subsum += guest * candidate
    total += subsum
  return total

right = maximum * 2
left = minimum * 2
temp = {}
while left < right:
  target_x = int((right + left) / 2)
  target_num = count_more_than(target_x)
  temp[target_x] = target_num
  if target_num > M:
    left = target_x + 1# increase left
  elif target_num < M:
    right = target_x - 1# decrease right
  else:
    break # found

target_sum = sum_more_than(target_x)
if target_num == M:
  pass
elif target_num < M:
  more_target_num = -1
  for idx in range(target_x - 1, minimum * 2, - 1):
      if idx not in temp:
        temp[idx] = count_more_than(idx)
      if temp[idx] > M:
        more_target_num = temp[idx]
        break
  more_target_sum = sum_more_than(idx)
  diff = int((more_target_sum - target_sum) / (more_target_num - target_num))
  target_sum += diff * (M - target_num)
elif target_num > M:
  less_target_num = -1
  for idx in range(target_x + 1, maximum * 2):
      if idx not in temp:
        temp[idx] = count_more_than(idx)
      if temp[idx] < M:
        less_target_num = temp[idx]
        break
  less_target_sum = sum_more_than(idx)
  diff = int((target_sum - less_target_sum) / (target_num - less_target_num))
  target_sum -= diff * (target_num - M)
#print("%d,%d,%d" % (target_x, target_num, target_sum))
print(target_sum)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
a = np.array([list(map(int,input().split()))])
a2 = (a+a.T).reshape(1,n*n)[0]
a2.sort()
print(a2[-m:].sum())

Submission status: Runtime Error

Solution code:
# input
s1 = str(input())
s2 = str(input())
s1s = s1.split(' ')
N = int(s1s[0])
M = int(s1s[1])
guests = list(map(int, s2.split(' ')))

# preprocess (counting)
maximum = guests[0]
minimum = guests[0]
for guest in guests:
  if maximum < guest:
    maximum = guest
  if minimum > guest:
    minimum = guest

COUNT_SUM = [0] * (maximum + 1)
for guest in guests:
  COUNT_SUM[guest] += 1 # count

TOTAL_SUM = [] # cumulative sum
for idx in range(1, len(COUNT_SUM)): # COUNT_SUM[i]: number of guests with value less than i 
  # first use cumulative sum
  if COUNT_SUM[idx] > 0:
    for _ in range(COUNT_SUM[idx]):
      if len(TOTAL_SUM) > 0:
        TOTAL_SUM.append(idx + TOTAL_SUM[-1])
      else:
        TOTAL_SUM.append(idx)
        
  # second use cumulative count
  COUNT_SUM[idx] = COUNT_SUM[idx] + COUNT_SUM[idx - 1]

def count_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    total += candidate
  return total

def sum_more_than(X):
  total = 0
  for guest in guests:
    target = X - guest
    if target < 0:
      candidate = N # every pair is OK
    elif target > maximum:
      candidate = 0
    else:
      candidate = N - COUNT_SUM[target - 1]
    subsum = TOTAL_SUM[N - 1] - TOTAL_SUM[N - candidate - 1] if candidate < N else TOTAL_SUM[N - 1]
    subsum += guest * candidate
    total += subsum
  return total

right = maximum * 2
left = minimum * 2
temp = {}
while left < right:
  target_x = int((right + left) / 2)
  target_num = count_more_than(target_x)
  temp[target_x] = target_num
  if target_num > M:
    left = target_x + 1# increase left
  elif target_num < M:
    right = target_x - 1# decrease right
  else:
    break # found

target_sum = sum_more_than(target_x)
if target_num == M:
  pass
elif target_num < M:
  more_target_num = -1
  for idx in range(target_x - 1, minimum * 2, - 1):
      if idx in temp:
          if temp[idx] > M:
              more_target_num = temp[idx]
              break
  more_target_sum = sum_more_than(idx)
  diff = int((more_target_sum - target_sum) / (more_target_num - target_num))
  target_sum += diff * (M - target_num)
elif target_num > M:
  less_target_num = -1
  for idx in range(target_x + 1, maximum * 2):
      if idx in temp:
          if temp[idx] < M:
              less_target_num = temp[idx]
              break
  less_target_sum = sum_more_than(idx)
  diff = int((target_sum - less_target_sum) / (target_num - less_target_num))
  target_sum -= diff * (target_num - M)
#print("%d,%d,%d" % (target_x, target_num, target_sum))
print(target_sum)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
a = [10**18] + sorted(map(int, input().split()), reverse=True)


def solve(x):
   count = 0
   j = N
   for i in range(1, N+1):
      while a[i] + a[j] < x:
         j -= 1
      count += j
   
   return count


left, right = 0, 10**18
while left < right - 1:
   mid = (left + right) // 2
   if solve(mid) >= M:
      left = mid

   else:
      right = mid

acc = a
acc[0] = 0
for i in range(N):
   acc[i+1] += acc[i]

ans = 0
j = N
for i in range(1, N+1):
   while a[i] + a[j] < left+1:
      j -= 1
   ans += a[i]*j + acc[j]
   M -= j

if M:
   ans += left * M

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
B=[0]*N
B[-1]=A[-1]
for i in range(1,N):
    B[-1-i]=B[-i]+A[-i-1]

L=[0]*N
Max=A[-1]*2+1
Min=A[0]*2
s=0

while(s!=M):
    s=0
    l=Max
    r=Min
    C=(l+r)//2
    c=0
    for i in range(N):
        w=C-A[i]
        t=N-bisect.bisect(A,w)
        s+=t

    if(s<M):
        if(Max==C):
            break
        Max=C
    elif(s>M):
        if(Min==C):
            break
        Min=C
#print(C,M,s)
if(s-M==0):
        S=0
        for i in range(N):
            w=C-A[i]
            a=bisect.bisect(A,w)
            t=N-a
            if t>0:
                S+=t*A[i]+B[-t]
        ans=S
else:            
    J=0
    LISTX=[]
    cX=s-M
    C1=C
    while(cX>0):
        S=0
        for i in range(N):
            w=C-A[i]
            a=bisect.bisect(A,w)
            t=N-a
            if t>0:
                S+=t*A[i]+B[-t]
            if(N==a):
                a-=1
            x=A[i]+A[a]
            if x>C1 and abs(C-J)>abs(C-x):
                J=x
        C1=J
        LISTX.append(J)
        cX-=1
    ans=S-sum(LISTX)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A = np.sort(A)[::-1]
 
m = int(min(M,N))
num = np.zeros(m)
ans = np.zeros(1)
for n,a in enumerate(A):
  if n>m:break
  for nn,aa in enumerate(A):
    if nn>m:break
    num[nn] = int(a) + int(aa)
  num = np.sort(num)[::-1]
  ans = np.r_[ans,num]
  ans = np.sort(ans)[::-1][:M]

print(int(sum(ans[:M])))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input():
    return sys.stdin.readline()

def search_max(d):
    return max(d, key=lambda x:d[x])

if __name__=="__main__":
    n,m =  map(int,input().split())
    l = [int(i) for i in input().split()]
    l.sort()
    l = deque(l[::-1])
    d = {(0,1):l[0]+l[1],(1,1):l[1]+l[1]}
    happiness = l[0]*2
    m_ = 1

    while m > m_:
        key = search_max(d)
        s = d[key]
        happiness += s*2
        if key[0] == key[1]:
            happiness -= s
            m_ -= 1
            if key[0]+1 <= n-1:
                d[(key[0]+1,key[1]+1)] = l[key[0]+1] + l[key[1]+1]
        if key[1] + 1 <= n-1:
            d[(key[0],key[1]+1)] = l[key[0]] + l[key[1]+1]
        d.pop(key)
        m_ += 2
        if m_ > m:
            happiness -= s
    print(happiness)