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: Wrong Answer

Solution code:
from bisect import bisect_left
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
l, r = 0, A[-1]*2+1
while r - l > 1:
  mid = (l+r)//2
  count = 0
  for num in A:
    count += N-bisect_left(A, mid-num)
  if count >= K:
    l = mid
  else:
    r = mid
AA = list(accumulate(A))
count = 0
answer= 0
for num in A[::-1]:
  index = bisect_left(A, l-num)
  if index > 0:
    answer += AA[-1]-AA[min(max(N-1, N-K+count-1), index-1)]
  else:
    answer += AA[min(max(N-1, N-K+count-1), N-1)]
  answer += min(N-index, K-count)*num
  count += N-index
  if count >= K:
    break
print(answer)

Submission status: Wrong Answer

Solution code:
class NTT:
    def __init__(self, convolution_rank, binary_level):
        self.cr = convolution_rank
        self.bl = binary_level
        self.modulo_list = [1]*convolution_rank
        self.primal_root_list = [1]*convolution_rank
        self.bin_list = [1]*(binary_level+1)
        self.primal_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        self.inverse_base_matrix = [[0 for _ in range(binary_level+1)] for __ in range(convolution_rank)]
        for i in range(binary_level):
            self.bin_list[i+1] = self.bin_list[i] * 2
    
    def doubling(self, n, m, modulo=0):
        y = 1
        tmp = m
        bas = n
        while tmp:
            if tmp % 2:
                y *= bas
                if modulo:
                    y %= modulo
            bas *= bas
            if modulo:
                bas %= modulo
            tmp >>= 1
        return y
    
    def powlimit(self, n):
        y = 1
        cnt = 0
        while y < n:
            y *= 2
            cnt += 1
        return y, cnt
    
    def IsPrime(self, num):
        p = 2
        if num <= 1:
            return False
        while p * p <= num:
            if num % p == 0:
                return False
            p += 1
        return True
    
    def extgcd(self, a, b, c):
        if b < 0:
            a, b, c = -a, -b, -c
        x, y, u, v, k, l = 1, 0, 0, 1, a, b
        while l:
            x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
            k, l = l, k % l
        if c % k:
            return "No Solution"
        return x * c, y * c
    
    def inved(self, a, modulo):
        x, y = self.extgcd(a, modulo, 1)
        return (x+modulo)%modulo
    
    def root_manual(self):
        for i in range(self.cr):
            r = 1
            flg = True
            while flg:
                fflg = True
                for j in range(self.bl):
                    if self.doubling(r, self.bin_list[j], self.modulo_list[i]) == 1:
                        fflg = False
                if self.doubling(r, self.bin_list[-1], self.modulo_list[i]) != 1:
                    fflg = False
                if fflg:
                    flg = False
                else:
                    r += 1
                    if r >= self.modulo_list[i]:
                        break
            self.primal_root_list[i] = r
    
    def make_prime_root(self):
        cnt = 0
        j = 1
        last = self.bin_list[-1]
        while cnt < self.cr:
            if self.IsPrime(j*last+1):
                flg = True
                r = 1
                while flg:
                    fflg = True
                    for i in range(self.bl):
                        if self.doubling(r, self.bin_list[i], j*last+1) == 1:
                            fflg = False
                    if self.doubling(r, last, j*last+1) != 1:
                        fflg = False
                    if fflg:
                        flg = False
                    else:
                        r += 1
                        if r >= j*last+1:
                            break
                if flg==False:
                    self.modulo_list[cnt] = j*last+1
                    self.primal_root_list[cnt] = r
                    cnt += 1
            j += 2
    
    def make_basis(self):
        for i in range(self.cr):
            for j in range(self.bl):
                tmp = self.doubling(2, self.bl-j)
                self.primal_base_matrix[i][j] = self.doubling(self.primal_root_list[i], tmp, self.modulo_list[i])
                self.inverse_base_matrix[i][j] = self.inved(self.primal_base_matrix[i][j], self.modulo_list[i])
    
    def NTT(self, f, n, idx, depth, inverse=False, surface=True):
        mod = self.modulo_list[idx]
        i2 = self.inved(2, mod)
        if inverse:
            seed = self.primal_base_matrix[idx][depth]
        else:
            seed = self.inverse_base_matrix[idx][depth]
        if n == 1:
            return f
        if n == 2:
            xf = [(f[0] + f[1])%mod, (f[0] - f[1])%mod]
            if inverse * surface:
                xf[0] *= i2
                xf[0] %= mod
                xf[1] *= i2
                xf[1] %= mod
            return xf
        hn = n // 2
        fe = [f[2*i+0] for i in range(hn)]
        fo = [f[2*i+1] for i in range(hn)]
        fe = self.NTT(fe, hn, idx, depth-1, inverse, False)
        fo = self.NTT(fo, hn, idx, depth-1, inverse, False)
        xf = [0 for _ in range(n)]
        grow = 1
        for i in range(hn):
            right = (fo[i] * grow) % mod
            xf[i+0*hn] = (fe[i] + right) % mod
            xf[i+1*hn] = (fe[i] - right) % mod
            grow *= seed
            grow %= mod
        if inverse * surface:
            invn = self.inved(n, mod)
            for i in range(n):
                xf[i] *= invn
                xf[i] %= mod
        return xf
    
    def second_NTT(self, f, n, idx, depth, inverse=False):
        res = [0 for _ in range(n)]
        tmp = [0 for _ in range(n)]
        MOD = self.modulo_list[idx]
        ipl = self.inved(n, MOD)
        for i in range(n):
            bas = 1
            pos = 0
            for j in range(depth, 0, -1):
                pos += bas * ((i>>(j-1)) % 2)
                bas *= 2
            res[i] = f[pos]
        for i in range(depth):
            grow = 1
            seed = inverse * self.primal_base_matrix[idx][i+1] + (1 - inverse) * self.inverse_base_matrix[idx][i+1]
            for k in range(1<<i):
                for j in range(1<<(depth-i-1)):
                    tmp[j*(1<<(i+1))+k+0*(1<<i)] = (res[j*(1<<(i+1))+k] + grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                    tmp[j*(1<<(i+1))+k+1*(1<<i)] = (res[j*(1<<(i+1))+k] - grow * res[j*(1<<(i+1))+k+(1<<i)]) % MOD
                grow *= seed
                grow %= MOD
            for j in range(n):
                res[j] = tmp[j]
        if inverse:
            for i in range(n):
                res[i] *= ipl
                res[i] %= MOD
        return res
    
    def CRT(self, num, a_list, m_list):
        r = a_list[0]
        bas = m_list[0]
        x, y = 0, 0
        for i in range(1, num):
            x, y = self.extgcd(bas, -m_list[i], a_list[i]-r)
            r += bas * x
            bas *= m_list[i]
        return r % bas

N, M = map(int, input().split())
ntt = NTT(2, 27)
ntt.make_prime_root()
ntt.make_basis()
#A = list(map(int, input().split()))
A = [2 for _ in range(100000)]
m = max(A)
pl, cnt = ntt.powlimit(2*m+2)
X = [0 for _ in range(pl)]
for i in range(N):
    X[A[i]] += 1
X1 = ntt.second_NTT(X, pl, 0, cnt)
X2 = ntt.second_NTT(X, pl, 1, cnt)
Z1 = [X1[i]*X1[i]%ntt.modulo_list[0] for i in range(pl)]
Z2 = [X2[i]*X2[i]%ntt.modulo_list[1] for i in range(pl)]
Z1 = ntt.second_NTT(Z1, pl, 0, cnt, True)
Z2 = ntt.second_NTT(Z2, pl, 1, cnt, True)
Z = [ntt.CRT(2, [Z1[i], Z2[i]], ntt.modulo_list) for i in range(pl)]
pnt = 2*m
hap = 0
num = 0
while num < M:
    if Z[pnt] + num < M:
        hap += Z[pnt] * pnt
        num += Z[pnt]
    else:
        hap += pnt * (M - num)
        num = M
    pnt -= 1
print(hap)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

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

ok, ng = 0, 10**18+1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    ok_flag = True
    cnt = 0
    # print('-----')
    # print(ok,ng,mid)
    for i,a in enumerate(al):
        rem = mid-a
        cnt_a = n-bisect_left(al,rem)
        # cnt_a = min(n-i-1, cnt_a)
        cnt += cnt_a
        # print(i,a,cnt_a)
    if cnt >= m:
        ok = mid
    else:
    	ng = mid

min_sum = ok
cum_sums = [0]
csum = 0
for a in al:
    csum += a
    cum_sums.append(csum)
    
# print(min_sum)

ans = 0
cnt = 0
for i,a in enumerate(al):
    rem = min_sum - a
    ind = bisect_left(al, rem)
    # ind = ind if 0 <= ind < n else None
    # ind = max(i+1,ind)
    csum = cum_sums[n] - cum_sums[ind]
    print(i,a,csum)
    ans += csum
    ans += a*(n-ind)
    cnt += (n-ind)

ans -= (cnt-m)*min_sum

print(ans)
# print(min_sum)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    A = LI()
    a = sorted(A,reverse=True)

    high = a[0] * 2
    low = 0
    while high > low + 1:
        mid = (high + low) // 2

        cnt = 0
        j = N - 1
        for i in range(N):
            while a[i] + a[j] < mid:
                j -= 1
                if j < 0: break
            else:
                cnt += (j+1)
                continue
            break
        if cnt <= M:
            high = mid
        else:
            low = mid

    s = [a[0]]
    for i in range(1,N):
        s.append(s[-1]+a[i])

    ans = 0
    cnt = 0
    j = N - 1
    for i in range(N):
        while a[i] + a[j] < low:
            j -= 1
            if j < 0: break
        else:
            ans += a[i] * (j+1) + s[j]
            cnt += j + 1
            continue
        break

    print(ans - (cnt-M) * low)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    A = LI()
    a = sorted(A,reverse=True)

    high = a[0] * 2
    low = 0
    while high > low + 1:
        mid = (high + low) // 2

        cnt = 0
        j = N - 1
        for i in range(N):
            while a[i] + a[j] < mid:
                j -= 1
                if j < 0: break
            else:
                cnt += (j+1)
                continue
            break
        if cnt < M:
            high = mid
        else:
            low = mid

    s = [a[0]]
    for i in range(1,N):
        s.append(s[-1]+a[i])

    ans = 0
    cnt = 0
    j = N - 1
    for i in range(N):
        while a[i] + a[j] < low:
            j -= 1
            if j < 0: break
        else:
            ans += a[i] * (j+1) + s[j]
            cnt += j + 1
            continue
        break

    print(ans - (cnt-M) * low)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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 Counter:
    def __init__(self):
        self.dict = {}

    def add(self,x):
        if x in self.dict: self.dict[x] += 1
        else: self.dict[x] = 1

    def decrement(self,x):
        self.dict[x] -= 1
        if self.dict[x] <= 0:
            del self.dict[x]

    def get_dict(self):
        return self.dict




def fft(A,B,fft_len=2*10**5):
    x = irfft(rfft(A,fft_len) * rfft(B,fft_len))+0.5
    return x.astype(int)


def main():
    N,M=mi()
    A=list(mi())

    counter = Counter()
    for a in A: 
        counter.add(a)
    
    count_map = counter.get_dict()
    F=[0]*2*10**5
    for a,count in count_map.items():
        F[a] = count
    
    G = fft(F,F)

    ans = 0
    handshake = M
    for x in range(len(G)-1,1,-1):
        if G[x] <= 0: continue
        count = G[x]
        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: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
N,M = map(int,input().split())
A = list(map(int,input().split()))
a = np.zeros(10**5+1)
for i in range(N):
    a[A[i]] += 1
b = rfft(a,2*10**5+1)
b = irfft(b*b,2*10**5+1)
b = np.rint(b).astype(np.int64)
c = 0
ans = 0
for n in range(2*10**5,2,-1):
    if c+b[n]<M:
        c += b[n]
        ans += b[n]*n
    else:
        ans += (M-c)*n
        c = M
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
N,M = map(int,input().split())
A = list(map(int,input().split()))
a = np.zeros(10**5+1)
for i in range(N):
    a[A[i]] += 1
b = rfft(a,2*10**5+1)
b = irfft(b*b,2*10**5+1)
b = np.rint(b).astype(np.int64)
c = 0
ans = 0
for n in range(2*10**5,2,-1):
    if c+b[n]<=M:
        c += b[n]
        ans += b[n]*n
    else:
        ans += (M-c)*n
        c = M
        break
print(ans)

Submission status: Wrong Answer

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

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

# DBG = []

def find(power):
    cnt = 0
    sam = 0
    for a in A:
        left = -1
        right = N
        while right-left>1:
            mid = left + (right-left)//2
            if a+A[mid] >= power:
                right = mid
            else:
                left = mid
        cnt += (N-right)
        sam += (AS[N]-AS[right]) + (N-right)*a
        # for i in range(right, N):
        #     DBG.append((A[i], a))
    return cnt, sam

left = 0
right = 10**5
while right-left>1:
    mid = left + (right-left)//2
    cnt, sam = find(mid)
    if cnt>M:
        left = mid
    else:
        right = mid

# ap+aq<=leftを満たすものの和を求める
cnt, ans = find(left)
print(ans - (cnt-M)*left)

Submission status: Wrong Answer

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

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

def find(power):
    cnt = 0
    sam = 0
    for a in A:
        left = -1
        right = N
        while right-left>1:
            mid = left + (right-left)//2
            if a+A[mid] >= power:
                right = mid
            else:
                left = mid
        cnt += (N-right)
        sam += (AS[N]-AS[right]) + (N-right)*a
    return cnt, sam

left = 0
right = 10**5
while right-left>1:
    mid = left + (right-left)//2
    cnt, sam = find(mid)
    if cnt<M:
        right = mid
    else:
        left = mid

# ap+aq<=leftを満たすものの和を求める
cnt, ans = find(left)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
チルノ（無色）のプログラミング教室～☆

こんなの無色コーダーのレベルじゃないよ～
え？　ABC D-Pairs とほとんど同じ方針？
こんな典型問題も解けないから灰色にすらなれない無色なんだよ、だって？
うわーん、無色っていうなー！！！
"""


def get_count(x):
    """
    :return: x 以上となる組の数
    """
    cnt = 0
    for i in range(N):
        cnt += bisect_left(A, x-A[i])
    res = N**2 - cnt
    return res

def binary_search_int(ok, ng, test):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if test(mid):
            ok = mid
        else:
            ng = mid
    return ok

def test(x):
    return get_count(x) >= M

def get_sum(x):
    res = 0
    cnt = 0
    for i in range(N):
        temp = bisect_left(A, x-A[i])
        res += A[i]*(N - temp) + B[-1] - B[temp]
        cnt += N - temp
    return res - x*(cnt-M)

################################################################

from bisect import *
from itertools import accumulate

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

print(get_sum(binary_search_int(0, 2*10**5, test)))

Submission status: Wrong Answer

Solution code:
import bisect
import copy

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

a.sort()
asum = [0]
tmp = 0
for i in range(n):
    tmp += a[i] 
    asum.append(tmp)

lb = 1
ub = 10**5 + 1
while ub - lb > 1:
    cx = (ub+lb)//2
    cnt = 0
    total = 0
    for ca in a:
        cy = cx - ca
        ci = bisect.bisect_left(a, cy)
        cnt += n - ci
        total += asum[n] - asum[ci] + (n - ci) * ca
    if cnt >= m:
        lb = cx
        ans = copy.deepcopy(total) - (cnt - m) * cx
    else:
        ub = cx

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
if n==1:
    print(a[0]*2)
    exit()
from bisect import bisect_left,bisect_right
#幸福度がx以上がm以上か？
def f(x):
    global n,a
    ret=0
    for i in range(n):
        ret+=(n-bisect_left(a,x-a[i]))
    return ret
l,r=a[0]+a[1],a[n-1]+a[n-2]
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=m:
        l=k
    else:
        r=k
#print(l,r)
#print(f(l),f(r))
if f(r)>=m:
    co,ans=0,0
    for i in range(n):
        co+=(n-bisect_right(a,r-a[i]))
        ans+=(n-bisect_right(a,r-a[i]))*a[i]
    print(2*ans+(m-co)*r)
else:
    co,ans=0,0
    for i in range(n):
        co+=(n-bisect_right(a,l-a[i]))
        ans+=(n-bisect_right(a,l-a[i]))*a[i]
    print(2*ans+(m-co)*l)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
if n==1:
    print(a[0]*2)
    exit()
from bisect import bisect_left
#幸福度がx以上がm以上か？
def f(x):
    global n,a
    ret=0
    for i in range(n):
        ret+=(n-bisect_left(a,x-a[i]))
    return ret
l,r=a[0]+a[1],a[n-1]+a[n-2]
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=m:
        l=k
    else:
        r=k
#print(l,r)
#print(f(l),f(r))
if f(r)>=m:
    co=f(r)-m
    ans=0
    for i in range(n):
        ans+=(n-bisect_left(a,r-a[i]))*a[i]
    print(2*ans-co*r)
else:
    co=f(l)-m
    ans=0
    for i in range(n):
        ans+=(n-bisect_left(a,l-a[i]))*a[i]
    print(2*ans-co*l)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
if n==1:
    print(a[0]*2)
    exit()
from bisect import bisect_left
#幸福度がx以上がm以上か？
def f(x):
    global n,a
    ret=0
    for i in range(n):
        ret+=(n-bisect_left(a,x-a[i]))
    return ret
l,r=a[0]+a[1]-1,a[n-1]+a[n-2]+1
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=m:
        l=k
    else:
        r=k
#print(l,r)
#print(f(l),f(r))
if f(r)>=m:
    co=f(r)
    ans=0
    for i in range(n):
        ans+=(n-bisect_left(a,r-a[i]))*a[i]
    print(2*ans-(co-m)*r)
else:
    co=f(l)
    ans=0
    for i in range(n):
        ans+=(n-bisect_left(a,l-a[i]))*a[i]
    print(2*ans-(co-m)*l)

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))

s=[0]*n
a.sort()
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]
res=0
l=0
r=2*a[-1]
while r>l+1:
    x=(l+r)//2
    res=0
    for ai in a:
        j=x-ai
        cnt=bisect.bisect_left(a,j)
        res+=(n-cnt)
    if res<m:
        r=x
    else:
        l=x
ans=0
c=0
for ai in a:
    cnt=bisect.bisect_left(a,l-ai)
    ans=ans+ai*(n-cnt)+(s[-1]-s[cnt-1]) if cnt!=0 else ans+ai*(n-cnt)+s[-1]
    c+=(n-cnt)
ans-=(c-m)*l
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = [0]
for ai in a:
    s.append(ai + s[-1])

def count(x, accum=False):
    ret = 0
    for ai in a:
        lo, hi = -1, n
        while hi - lo > 1:
            mid = (lo + hi) // 2
            if ai + a[mid] >= x:
                lo = mid
            else:
                hi = mid
        ret += ai * hi + s[hi] if accum else hi
    return ret

lo, hi = 0, 1000000000
while hi - lo > 1:
    mid = (lo + hi) // 2
    if count(mid) >= m:
        lo = mid
    else:
        hi = mid
print(count(lo, accum=True) - (count(lo) - m) * hi)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = a[0]
t = 0
j = 1
ret = 0
for i in range(n):
    if m <= 0:
        break
    s -= a[i]
    ret += a[i] * 2
    m -= 1
    while j < n and (i >= n - 1 or a[i + 1] + a[i + 1] < a[i] + a[j]):
        if m < i * 2:
            for k in range(i):
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
        else:
            ret += t * 2 + a[j] * i * 2
            m -= i * 2
        s += a[j]
        j += 1
    num = (j - i - 1) * 2
    if m < num:
        for k in range(i + 1, j):
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
    else:
        ret += s * 2 + a[i] * num
        m -= num
    t += a[i]
print(ret)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = a[0]
t = 0
j = 1
ret = 0
for i in range(n):
    if m <= 0:
        break
    s -= a[i]
    ret += a[i] * 2
    m -= 1
    while j < n and (i >= n - 1 or a[i + 1] + a[i + 1] <= a[i] + a[j]):
        if m < i * 2:
            for k in range(i):
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
        else:
            ret += t * 2 + a[j] * i * 2
            m -= i * 2
        s += a[j]
        j += 1
    num = (j - i - 1) * 2
    if m < num:
        for k in range(i + 1, j):
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
    else:
        ret += s * 2 + a[i] * num
        m -= num
    t += a[i]
print(ret)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
s = a[0]
t = 0
j = 1
ret = 0
for i in range(n):
    s -= a[i]
    ret += a[i] * 2
    m -= 1
    while j < n and (i >= n - 1 or a[i + 1] + a[i + 1] <= a[i] + a[j]):
        if m < i * 2:
            for k in range(i):
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
                if m > 0:
                    ret += a[j] + a[k]
                    m -= 1
        else:
            ret += a[j] * i * 2 + t * 2
            m -= i * 2
        s += a[j]
        j += 1
    num = (j - i - 1) * 2
    if m <= num:
        for k in range(i + 1, j):
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
            if m > 0:
                ret += a[i] + a[k]
                m -= 1
        break
    m -= num
    ret += s * 2 + a[i] * num
    t += a[i]
print(ret)

Submission status: Wrong Answer

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

d = {}
for i in range(cut):
    for j in range(i, cut):  # 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: Wrong Answer

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

ans = 0
# 00, 01, 10, 11, 12, 21, 22, 23, 32, 33, ..., 14, 41, 25, 52, ...
cnt = 0
for base in range(n):
    for hoge in range(1, n-base):
        for l, r in ([(base, base), (base, base+hoge), (base+hoge, base)] if hoge == 1 else [(base, base+hoge), (base+hoge, base)]):
            if l >= n or r >= n:
                break
            ans += ttt[l] + ttt[r]
            cnt += 1  # 1e10 .... 
            if cnt == k:
                print(ans)
                exit()

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(' ')))
ttt = sorted(list(map(int, input().split(' '))))[::-1]
d = {}
ans = 0
# 00, 01, 10, 11, 12, 21, 22, 23, 32, 33, ..., 14, 41, 25, 52, ...
cnt = 0
for base in range(n):
    for hoge in range(1, n):
        for l, r in ([(base, base), (base, base+hoge), (base+hoge, base)] if hoge == 1 else [(base, base+hoge), (base+hoge, base)]):
            if l >= n or r >= n:
                continue
            ans += ttt[l] + ttt[r]
            cnt += 1
            if cnt == k:
                print(ans)
                exit()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
c = [a[i]+a[j] for i in range(n) for j in range(n) ]
c.sort(reverse=True)
print(c)
print(sum(c[:m]))

Submission status: Wrong Answer

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


def get_count(tot):
    '''
    tot以上を満たす幸福度の握手の個数を数える
    '''
    ret = 0
    for i in range(N):
        cnt = bisect_left(A, tot-A[i])
        ret += N - cnt
    return ret


# 右からの累積和
Asum = A[:]
for i in range(N-2, -1, -1):
    Asum[i] += Asum[i+1]


def get_sum(tot):
    '''
    左端を固定した時の右端の個数分だけ左端を足し、右端の区間和（累積和）も足す。
    '''
    ret = 0
    for i in range(N):
        idx = bisect_left(A, tot-A[i])
        cnt = N - idx
        ret += A[i]*cnt
        # print(idx)
        if idx == N:
            continue
        ret += Asum[idx]
        # print(f'ret = {ret}')
    return ret


# M回握手できる上限を求める
ok = 0
ng = 10**12
while ok + 1 != ng:
    md = (ok + ng)//2
    if M <= get_count(md):
        ok = md
    else:
        ng = md
# print(ok)
# print(get_sum(ok+1))
# print(M - get_count(ok+1))
# print(Asum)
ans = get_sum(ok+1) + (M - get_count(ok+1))*ok

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, M = map(int, input().split())
A = list(sorted(map(int, input().split())))
S = sum(A)
def check(x):
    cnt = 0
    for a in A:
        l = -1
        r = N
        while r - l > 1:
            m = (l + r) // 2
            if A[m] + a >= x:
                r = m
            else:
                l = m
        cnt += N - r
    return cnt < M

left = 0
right = 10 ** 6
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

ans = 0
cnt = 0
for a in A:
    l = -1
    r = N
    while r - l > 1:
        m = (l + r) // 2
        if A[m] + a >= left:
            r = m
        else:
            l = m
    cnt += (N - r)
    ans += (N - r) * a + S - sum(A[:r])
    if cnt > M:
        diff = cnt - M
        ans -= diff * a + sum(A[r:r + diff])
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
s,t =map(int,input().split())
l = list(map(int,input().split()))
k = [0]
n = 0
l.sort()
l.reverse()
for i in range(round(math.sqrt(t))):
  for j in range(round(math.sqrt(t))):
    k.append(l[i]+l[j])
k.sort()
k.reverse()
for i in range(t):
  n = n+k[i]
print(n)

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft, irfft

N, M = map(int, input().split())
*A, = map(int, input().split())
B = np.zeros(2*10**5)
for a in A:
    B[a] += 1

L = 2*10**5
FB = rfft(B, L)
C = np.rint(irfft(FB*FB)).astype(int)

ans = 0
for i in range(L-1, -1, -1):
    c = C[i]
    if not c:
        continue
    print(i, c, M)
    if M - c > 0:
        ans += i*c
        M -= c
    else:
        ans += i*M
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
cumax=(2*10**5)+10
cuml=[0]*cumax
#print(A)
ind=0
l=[]
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
lr=[]
v=[]
for i in range(len(key)):
    lr.append([0,l[i][0]])
    v.append(l[i][1])
for i in range(len(v)):
    l=lr[i][0]
    r=lr[i][1]
    cuml[l]=cuml[l]+v[i]
    if r+1<cumax:
        cuml[r+1]=cuml[r+1]-v[i]
for i in range(cumax-1):
    cuml[i+1]=cuml[i+1]+cuml[i]
#print(cuml)
maxind=2*10**5
minind=0
while maxind-minind>1:
    piv=minind+(maxind-minind)//2       #pivは握手の幸福度
    cnt=0
    for i in range(N):
        x=piv-A[i]
        cnt=cnt+cuml[max(x,0)]
    if cnt<=M:
        maxind=piv
    else:
        minind=piv
    #print(cnt,maxind,piv,minind)
#print(minind)
thr=minind
cuml2=[0]*(N+1)
A.sort(reverse=True)
for i in range(N):
    cuml2[i+1]=cuml2[i]+A[i]
#print(cuml2,thr,A)
ans=0
counts=0
#print(cuml[0:10])
for i in range(N):
    x=thr-A[i]
    #print(x)
    cnt=cuml[max(x,0)]
    #print(cnt)
    ans=ans+(A[i]*cnt)+cuml2[cnt]
    counts=counts+cnt
ans=ans-(counts-M)*thr
#print()
print(ans)