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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from bisect import bisect_left

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

b = [0]*(n+1)
a.sort()
for i in range(n):
  b[i+1] = b[i]+a[i]

def is_ok(arg):
    c = 0
    f = False
    for i in a:
      if c >= m:
        break
      c += (n-bisect_left(a,arg-i))
    if c >= m:
      f = True
    return f

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

x = bisect_ok(2*a[-1]+1,1)
ans = 0
cnt = 0
for i in a:
  ind = n-bisect_left(a,x-i)
  cnt += ind
  ans += i*ind+(b[-1]-b[n-ind])
if cnt > m:
  ans -= x*(cnt-m)
print(ans)

Submission status: Accepted

Solution code:
import bisect


def is_ok(a, target, m):
    num = 0
    for val in a:
        index = bisect.bisect_left(a, target - val)
        num += len(a) - index
    if num <= m:
        return True
    else:
        return False


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

a.sort()

ok, ng = 10 ** 10, -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(a, mid, m):
        ok = mid
    else:
        ng = mid

rui = [0] * (n + 1)

for i in range(n):
    rui[i+1] = rui[i] + a[i]

cnt = 0
ret = 0

for val in a:
    index = bisect.bisect_left(a, ok - val)
    num = len(a) - index
    cnt += num
    ret += (num * val) + (rui[-1] - rui[index])

ret += (m - cnt) * ng

print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


import numpy as np


def main():
    N, M = geta(int)
    A = np.array(list(geta(int)))
    A.sort()

    def c(x):
        """
        @return  # of handshake where hapiness >= x
        """
        X = np.searchsorted(A, x - A)
        return N * N - X.sum()

    left, right = 0, 2 * A[-1] + 1

    while left + 1 < right:
        middle = (left + right) // 2
        if c(middle) >= M:
            left = middle
        else:
            right = middle

    ans = 0
    Acum = np.zeros(N + 1, np.int64)
    Acum[:-1] = np.cumsum(A[::-1])[::-1]
    X = np.searchsorted(A, right - A)

    ans = Acum[X].sum() + (A * (N - X)).sum()

    ans += left * (M - (N * N - X.sum()))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import bisect
import itertools
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**5)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N, M = geta(int)
    A = list(geta(int))
    A.sort()

    def c(x):
        """
        @return  # of handshake where hapiness >= x
        """
        ret = 0
        for a in A:
            ret += bisect.bisect_left(A, x - a)
        return N * N - ret

    left, right = 0, 2 * A[-1] + 1

    while left + 1 < right:
        middle = (left + right) // 2
        if c(middle) >= M:
            left = middle
        else:
            right = middle

    ans = 0
    Acum = list(itertools.accumulate(A[::-1]))[::-1]
    for a in A:
        idx = bisect.bisect_left(A, right - a)
        if idx < N:
            ans += Acum[idx] + a * (N - idx)
    ans += left * (M - c(right))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]

def cnt(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += bisect.bisect_left(A,x - a)
    return res

def ans(x,A,S):
    res = 0
    for i,a in enumerate(A):
        res += a*bisect.bisect_left(A,x-a) + S[bisect.bisect_left(A,x-a)]
    return res

top = A[-1]*2+1
bottom = 0
# mid以上が何個あるか
while top - bottom > 1:
    mid = (top + bottom)//2
    if n*n - cnt(mid,A,S) > m:
        bottom = mid
    else:
        top = mid

print(S[-1]*2*n - ans(top,A,S) + bottom*(m - (n*n - cnt(top,A,S))))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
# 文字列をinput()した場合、末尾に改行が入るので注意
def main():
  n,m=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  import bisect
  # 解説の二分探索
  # あるXを定め、X以上になる握手の組み合わせが何通りあるか計算。M個以上になる最大のXを探す
  # [l,r)半開区間
  l,r=0,a[-1]*2+1
  while r-l>1:
    x=(l+r)//2
    cnt=0
    for ai in a:
      cnt+=n-bisect.bisect_left(a,x-ai)
    # x以上がm個以上ある->x~r-1に求めるものがある
    if cnt>=m:
      l=x
    else:# x以上がm個未満ある->l~x-1に求めるものがある
      r=x
  x=(l+r)//2
  ans=0
  cnt=0
  a_=0
  cs_a=[0]
  for ai in a:
    a_+=ai
    cs_a.append(a_)
  for ai in a:
    bi=bisect.bisect_right(a,x-ai)
    cnt+=n-bi
    ans+=cs_a[-1]-cs_a[bi]+(n-bi)*ai
  print(ans+(m-cnt)*x)

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Accepted

Solution code:
from itertools import accumulate
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))
ruiseki = list(accumulate(A[::-1]))

def syakutori(mid):
    x = 0
    cnt = 0
    ans = 0
    for i in range(N)[::-1]: # 大きい方から
        while x < N:
            if A[i] + A[x] >= mid:
                cnt += N - x
                if N - x >= 1:
                    ans += A[i] * (N - x) + ruiseki[N - x - 1]
                break
            else:
                x += 1

    return cnt, ans

# 自分以上の数の個数がM個以上になる値のうち最大のもの
ok = 0
ng = 10 ** 15
while ok + 1 < ng:
    mid = (ok + ng) // 2
    cnt, ans = syakutori(mid)
    if cnt >= M:
        ok = mid
    else:
        ng = mid
# okで終わってる場合はcntがM個以上の場合があるから過分を引く
# ngで終わってる場合は残りM-cnt個のokを足す
print(ans + ok * (M - cnt))

Submission status: Accepted

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,M=nm()
A=nl()
A.sort()
S=[0]
S[0]=A[0]

for i in range(1,N):
    S.append(S[i-1]+A[i])

def clc_shake(x):#x以上の和
    tot=0
    for i in range(N):
        th=x-A[i]
        inds=bisect.bisect_left(A,th)
        tot+=(N-inds)
    return tot

l=0
r=2*(10**6)
c=0

while (l+1<r):
    c=(l+r)//2
    if(clc_shake(c)<M):
        r=c
    else:
        l=c


ans=0
for i in range(N):
        th=r-A[i]
        inds=bisect.bisect_left(A,th)
        if(inds!=0):
            ans+=((N-inds)*A[i]+(S[N-1]-S[inds-1]))
        else:
            ans+=((N-inds)*A[i]+(S[N-1]))


M2=M-clc_shake(r)
ans+=M2*(l)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys, heapq, bisect
sys.setrecursionlimit(300000)

def _count(A, n, v):
    ret = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ret += n - idx
    return ret

def _sum(A, n, v, sums):
    ss = 0
    for a in A:
        target = v - a
        idx = bisect.bisect_left(A, target)
        ss += sums[n] - sums[idx]
        ss += (n - idx) * a
    #print(mins)
    return ss

def solve(N: int, M: int, A: "List[int]"):
    A.sort()
    sums = [0]
    for a in A:
        sums.append(sums[-1] + a)
    l = -1
    r = max(A) * 2 + 1
    while r - l > 1:
        m = (r + l) // 2
        cnt = _count(A, N, m)
        if cnt >= M:
            l = m
        else:
            r = m
    cnt = _count(A, N, l)
    ret = _sum(A, N, l, sums)
    ret -= (cnt - M) * l
    print(ret)
    return ret


def solve_(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    q = [(-A[0] * 2, 0, 0)]
    ret = 0
    cnt = 0
    while cnt < M:
        s, i, j = heapq.heappop(q)
        ret += -s
        cnt += 1
        print(i, j)
        if i == j and i < N - 1:
            heapq.heappush(q, (-A[i] + -A[i + 1], i, i + 1))
        else:
            if cnt < M:
                ret += -s
                cnt += 1
                print(j, i)
            heapq.heappush(q, (-A[i + 1] + -A[j], i + 1, j))
            if j < N - 1:
                heapq.heappush(q, (-A[i] + -A[j + 1], i, j + 1))
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

A.sort(reverse = True)
#print(A)

ok = -1
ng = 10 ** 11
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    left, right = 0, N - 1
    cnt = 0
    while left <= N - 1 and right >= 0:
        if A[left] + A[right] >= mid:
            cnt += right + 1
            left += 1
        else:
            if right:
                right -= 1
            else:
                left += 1
    if cnt >= M:
        ok = mid
    else:
        ng = mid
#print(ok)

Acum = [0] + list(accumulate(A))
#print(Acum)

left, right = 0, N - 1
cnt = 0
answer = 0
while left <= N - 1 and right >= 0:
    if A[left] + A[right] >= ok:
        cnt += right + 1
        answer += (right + 1) * A[left] + Acum[right + 1]
        left += 1
    else:
        if right:
            right -= 1
        else:
            left += 1
        
answer -= (cnt - M) * ok
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
l = 0
r = 2*10**5+5


while l+1 < r:
    mid = (l+r) // 2
    
    m = 0
    for a in A:
        idx = bisect_left(A, mid-a)
        m += N-idx
        
    if m >= M: l = mid
    else: r = mid

s = [0] * (N+1)
for i in range(N):
    s[i+1] = s[i] + A[i]
    
ans = 0
m = 0
for a in A:
    idx = bisect_left(A, l-a)
    m += N-idx
    
    ans += s[N]-s[idx]
    ans += a*(N-idx)
    
ans -= (m-M)*l

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]

aa = [0]*(10**5+1)
aa_sum = [0]*(10**5+1)

for x in a:
    aa[x] += 1
    aa_sum[x] += x

for i in range(10**5)[::-1]:
    aa[i] = aa[i] + aa[i+1]
    aa_sum[i] = aa_sum[i] + aa_sum[i+1]


def count(x):
    cnt = 0
    sm = 0
    for i in range(n):
        if x-a[i] < 0:
            cnt += n
            sm += aa_sum[0]+n*a[i]
        elif x-a[i] > 10**5:
            continue
        else:
            cnt += aa[x-a[i]]
            sm += aa_sum[x-a[i]]+aa[x-a[i]]*a[i]

    return cnt, sm


bottom = 0
top = 10**6

while top - bottom > 1:
    mid = (top+bottom) // 2
    cnt, sm = count(mid)
    if cnt < m:
        top = mid
    else:
        bottom = mid

cnt, sm = count(bottom)
ans = sm - (cnt-m)*bottom

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    b = sorted(a)
    c = [0] + sorted(b)
    c = list(accumulate(c))
    a.sort(reverse=True)
    
    # mid以上の和をm個作れるならTrue
    def check(mid):
        total = 0
        for i in a:
            total += n - bisect_left(b, mid-i)
            if total >= m:
                return True
        return False

    l = 0
    r = 2*(10**5)+10
    # 最終的なlがm個以上作れる最小値
    while r - l > 1:
        mid = (l+r) // 2
        if check(mid):
            l = mid
        else:
            r = mid
    res = 0
    for i in a:
        d = bisect_left(b, r-i)
        if d == n:
            continue
        res += i * (n-d) + c[-1] - c[d]
        m -= n - d

    print(res + l*m)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N,M,*A = map(int, open(0).read().split())
A = np.sort(A)
B = np.cumsum(np.concatenate([[0],A[::-1]]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = np.sum(N-np.searchsorted(A,s-A))
  if cnt>=M:
    l = s
  else:
    r = s
ind = np.searchsorted(A,r-A)
M -= np.sum(N-ind)
ans = np.sum(B[N-ind]+A*(N-ind))+M*l
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open(0).read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**6
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from itertools import accumulate
N,M,*A = map(int, open(0).read().split())
A.sort()
B = list(accumulate(A[::-1]))
l = -1
r = 10**9
while l+1<r:
  s = (l+r)//2
  cnt = 0
  for c in A:
    i = bisect_left(A,s-c)
    cnt += N-i
  if cnt>=M:
    l = s
  else:
    r = s
ans = 0
for c in A:
  i = bisect_left(A,r-c)
  M -= N-i
  if i<N:
    ans += B[N-1-i]+c*(N-i)
ans += M*l
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    cnt = 0
    
    for Ai in A:
        cnt += N-bisect_left(A, x-Ai+1)
    
    return cnt<M

def binary_search():
    l, r = 0, 2*max(A)
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0]*(N+1)

for i in range(N):
    acc[i+1] = acc[i]+A[i]
    
cnt = 0
ans = 0

for Ai in A:
    j = bisect_left(A, border-Ai+1)
    cnt += N-j
    ans += (N-j)*Ai+acc[N]-acc[j]

ans += (M-cnt)*border
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n, m = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()

    def count(x): # the number of (i, j)s s.t. A[i] + A[j] >= x
        res = 0
        for a in A:
            idx = bisect_left(A, x - a)
            res += n - idx
        return res

    left = 0
    right = 200001
    while right - left > 1:
        mid = (left + right) // 2
        if count(mid) < m:
            right = mid
        else:
            left = mid

    x = right
    res = 0
    for a in A:
        idx = bisect_left(A, x - a)
        res += 2 * a * (n - idx)
    res += (x - 1) * (m - count(x))
    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(x):
  c = 0
  for y in a:
    ok = N
    ng = -1
    while ok - ng > 1:
      m = (ok + ng) // 2
      if a[m] + y >= x: ok = m
      else: ng = m
    c += N - ok
  return c >= M

ok = 0
ng = 10 ** 6
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m

l = ok + 1
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

res = 0
c = 0
for x in a:
  ok = N
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if a[m] + x >= l: ok = m
    else: ng = m
  c += N - ok
  res += cs[-1] - cs[ok] + x * (N - ok)

print(res + (l - 1) * (M - c))

Submission status: Accepted

Solution code:
from copy import copy

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

def count_more_x(x : int):
    j = 0
    ret = 0
    for i in range(len(b)):
        while j < len(a) and b[i]+a[j] < x:
            j += 1
        ret += j
    return n*n-ret

def sum_more_x(x : int):
    j = 0
    ret = 0
    for i in range(len(b)):
        while j < len(a) and b[i]+a[j] < x:
            j += 1
        ret += b[i]*(n-j)+c[j]
    return ret

lower = 0
upper = 1000000
while upper-lower > 1:
    middle = (upper+lower)//2
    if count_more_x(middle) < m:
        upper = middle
    else:
        lower = middle

left = lower

lower = 0
upper = 1000000
while upper-lower > 1:
    middle = (upper+lower)//2
    if count_more_x(middle) >= m:
        lower = middle
    else:
        upper = middle

right = upper

# print(left, right)
# print(count_more_x(right))
c = copy(a)
value = 0
for i in range(len(c)-1, -1, -1):
    value = value + c[i]
    c[i] = value
c.append(0)
ans = sum_more_x(right) + left*(m-count_more_x(right))
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

def count(x):
    ret = 0
    for a in A:
        ret += N - bisect_left(A, x - a)
    return ret

overEq = 0
less = 10**7
while less - overEq > 1:
    mid = (less + overEq) // 2
    if count(mid) >= M:
        overEq = mid
    else:
        less = mid

ans = 0
cnt = [0] * N
for a in A:
    i = (N - bisect_left(A, overEq - a))
    ans += i * a
    if i > 0:
        cnt[-i] += 1
for i in range(1, N):
    cnt[i] += cnt[i - 1]
for a, c in zip(A, cnt):
    ans += a * c

ans -= overEq * (count(overEq) - M)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]*=-1
a.sort()
b=[0]
for i in a:b.append(b[-1]+i)
ng=2*10**5+7
ok=-1
while ok+1!=ng:
  mid=(ng+ok)//2
  co=0
  for i in a:co+=br(a,-(mid+i))
  if co<m:ng=mid
  else:ok=mid
ans=0
co=0
for i in a:
  ind=br(a,-(ok+i)-1)
  co+=ind
  ans+=-b[ind]-i*ind
ans+=(m-co)*ok
print(ans)

Submission status: Accepted

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

# l[i] = (a[j] >= i を満たすjの個数)
l = [n for i in range(a[0]+1)]
for i in range(2, n+1):
    for j in range(a[-i], a[-i+1], -1):
        l[j] = n - i + 1

# 二分探索
# a[i] + a[j] >= x を満たす(i, j)がm組以上存在する最小のxを求める
start = 2 * a[-1]
stop = 2 * a[0]
while start < stop:
    i = (start + stop + 1) // 2
    num = 0
    for j in a:
        if i - j < 0:
            num += n
        elif i - j <= a[0]:
            num += l[i - j]
        else:
            break

    if num >= m:
        start = i
    else:
        stop = i - 1

num = 0
for i in a:
    if start - i < 0:
        num += n
    elif 0 <= start - i <= a[0]:
        num += l[start - i]
    else:
        break

# start <= a[i]+a[j] を満たす a[i]+a[j] を全て足す
ans = 0
for i in a:
    if start - i < 0:
        ans += 2 * i * n
    elif start - i <= a[0]:
        ans += 2 * i * l[start - i]
    else:
        break
ans -= (num - m) * start
print(ans)

Submission status: Accepted

Solution code:
def isok(arg):
    x = 0
    for i in a:
        if arg - i >= 0:
            if arg-i <= 10**5:
                x += cs[arg-i]
        else:
            x += n
    if x >= m:
        return True
    else:
        return False

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

n,m = map(int,input().split())
a = list(map(int,input().split()))
cs = [0]*(10**5+1)
for i in a:
    cs[i] += 1
for i in range(10**5):
    cs[10**5-i-1] += cs[10**5-i]
h = bisect(10**5*2+1,0)
count = 0
ans = 0
for i in a:
    num = max(0,h-i)
    if num <= 10**5:
        ans += 2*i*cs[num]
        count += cs[num]
ans -= (count-m)*h
print(ans)

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    a = list(map(int,input().split()))
    
    a.sort()
    cum = [0]
    for num in a:
        cum.append(cum[-1]+num)
    
    def power(x):
        count = 0
        for num in a:
            rest = x-num
            index = bisect.bisect_left(a,rest)
            count += N-index
        if count >= M:
            return True
        else:
            return False
    
    l,r = -1,10**10
    while r-l > 1:
        mid = (r+l)//2
        if power(mid):
            l = mid
        else:
            r = mid
            
    border = r
    
    count,ans = 0,0
    for num in a:
        rest = border-num
        index = bisect.bisect_left(a,rest)
        ans += (N-index)*num
        ans += cum[N]-cum[index]
        count += N-index
        
    print(ans+(M-count)*l)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
def justM(x,N):
    sum_=0
    for i in range(N):
        b=bisect.bisect_left(A,x-A[i])
        sum_+=N-b
    return sum_

N,M=map(int,input().split())
A=sorted(map(int,input().split()))
left,right=-1,(10**5)*2+1
while(right-left>1):
    mid=(right+left)//2
    s=justM(mid,N)
    if s<M:
        right=mid
    else:
        left=mid
D=left
r=[0]*(N+1)
ans=0
for i in range(N):
    r[i+1]=r[i]+A[i]
cnt=0
for i in range(N):
    b=bisect.bisect_left(A,D-A[i])
    ans+=A[i]*(N-b)+(r[N]-r[b])
    cnt+=N-b
print(ans-D*(cnt-M))

Submission status: Accepted

Solution code:
# 過去の提出を見ながら解いた

def main():
    N, M = map(int, input().split())
    *a, = map(int, input().split())
    a.sort()

    def count(mid) -> int:
        cnt = 0  # (i,j)>=mid の個数
        j = N  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
        for i in range(N):
            while j > 0 and a[i] + a[j - 1] >= mid:
                j -= 1
            # j==0 or a[i]+a[j]>=mid
            # j==0
            # 現在のiに対しすべてのaの要素が相方になる。
            # 一度そのようなiに達したら、それ以降のiはすべてこの条件を満たす。
            cnt += N - j  # iに対し[j,N)が相方になる
        return cnt

    def binary_search(*, ok: int, ng: int, is_ok: 'function') -> int:
        """あるペア和以上のみ採用する場合に
        M回以上握手できないようなペア和の上限"""
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    ma = binary_search(ok=2 * 10 ** 5 + 1, ng=0, is_ok=lambda mid: count(mid) < M)

    def accumulate(a):
        s = 0
        yield s
        for x in a:
            s += x
            yield s

    *acc, = accumulate(a)

    ans = 0
    j = N  # j: iと組んでペア和>=midを満たすjの下限, 初期値は範囲外=条件を満たすjはない
    for i in range(N):
        while j > 0 and a[i] + a[j - 1] >= ma:
            j -= 1
        ans += a[i] * (N - j) + acc[N] - acc[j]  # i側の寄与=ペア数,j側の寄与=acc
    ans += (ma - 1) * (M - count(ma))  # ペア和maではMペア組めないが、ma-1で埋められる

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from itertools import accumulate

def func(A, N, M, x):
    count = 0
    for Ai in A:
        idx = bisect_left(A, x - Ai)
        count += N - idx
    if count >= M:
        return True
    else:
        return False

def main():
    N, M = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    A_rev = list(reversed(A))
    B = [0] + list(accumulate(A_rev))
 
    min_ = 0
    max_ = 2 * 10 ** 5 + 1
    while max_ - min_ > 1:
        mid = (min_ + max_) // 2
        if func(A, N, M, mid):
            min_ = mid
        else:
            max_ = mid
    
    ans = 0
    count = 0
    for Ai in A_rev:
        idx = bisect_left(A, min_-Ai)
        ans += Ai * (N - idx) + B[N-idx]
        count += N - idx
    print(ans-(count-M)*min_)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect


def solve(mid):
    cnt = 0
    l = n
    r = n
    for i in range(n):
        while True:
            if l == 0:
                break
            if a[l - 1] < mid - a[i]:
                break
            l -= 1
        cnt += (r - l)
    return cnt >= m
    

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

ok = 0
ng = 2 * 10 ** 5 + 10
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + a[i]

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.bisect_left(a, ok - a[i])
    cnt += (r - l)
    ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)

Submission status: Accepted

Solution code:
import bisect


def solve(mid):
    cnt = 0
    l = n
    r = n
    for i in range(n):
        while True:
            if l == 0:
                break
            if a[l - 1] < mid - a[i]:
                break
            l -= 1
        cnt += (r - l)
    return cnt >= m
    

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

ok = 0
ng = 10 ** 18
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

ru = [0] * (n + 1)
for i in range(n):
    ru[i + 1] = ru[i] + a[i]

ans = 0
r = n
ok = ok + 1
cnt = 0
for i in range(n):
    l = bisect.bisect_left(a, ok - a[i])
    cnt += (r - l)
    ans += (r - l) * a[i] + (ru[r] - ru[l])
ans += (ok - 1) * (m - cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left as bi_l, bisect_right as bi_r
from itertools import accumulate

n, m, *a = map(int, sys.stdin.read().split())
a.sort()

def count(border):
  res = 0
  for x in a:
    b = border - x
    res += n - bi_l(a, b)
  return res

def main():
  lo, hi = 1, a[-1] * 2 + 1
  while lo + 1 < hi:
    border = (lo + hi) // 2
    if count(border) >= m:
      lo = border
    else:
      hi = border
  
  s = a.copy() + [0]
  *s, = accumulate(s[::-1])
  tot = 0
  for x in a:
    b = lo - x
    c = n - bi_l(a, b)
    tot += x * c + s[c]
  
  tot -= lo * (count(lo) - m)
  print(tot)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import bisect
def count(k):
    #幸福値がk以上となるような握手の総数
    cnt=0
    for i in range(n):
        cnt+=n-bisect.bisect_left(a,k-a[i])
    return cnt

l=0
r=2*10**5+10

while r-l>1:
    med=(r+l)//2
    if count(med)<m:
        r=med
    elif count(med)>=m:
        l=med
#合計がl以上の物の合計を足して、その値からl*(count(l)-m)を取ればいい

ans=0

dp=[0 for i in range(n+1)]
#dp[i]=aの後ろからi番目までの数の総数
for i in range(1,n+1):
    dp[i]=dp[i-1]+a[-i]

for i in range(n):
    x=a[i]
    index=n-bisect.bisect_left(a,l-x)
    ans+=dp[index]+x*index
    
print(ans-l*(count(l)-m))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi
#         print(now,ax,bi)
    return n**2-num

mi = a[0]*2-1
ma = a[-1]*2+1
kotae=ma
while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m#なんか判定
    if which:
        ma=now
        kotae=now
    else:
        mi=now+1
kotae-=1

suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]
    
ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,kotae-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*kotae)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()

    import bisect

    ok = 0
    ng = 2 * max(a) + 1

    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        count = 0
        i = 0
        for elem in a:
            minlim = mid - elem
            count += (n - bisect.bisect_left(a, minlim))

        if count >= m:
            ok = mid
        else:
            ng = mid

    from itertools import accumulate

    a_cum = list(accumulate(a[::-1]))
    a_cum = a_cum[::-1] + [0]
    ans = 0
    j = n
    cnt_over = 0

    for elem in a:
        minlim = ok - elem + 1
        idx = bisect.bisect_left(a, minlim)
        ans += a_cum[idx]
        ans += elem * (n - idx)
        cnt_over += (n - idx)

    ans += ok * (m - cnt_over)

    print(ans)


if __name__ == '__main__':
    main()