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:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>l:
      ans += C[-1]-C[j]+A[i]*(N-j)
      m += N-j
    j += 1
ans += (M-m)*l
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**8
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
ans = 0
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>=l:
      x = min(N-j,M-m)
      ans += C[-1]-C[N-x]+A[i]*x
      m += x
      if M==m:
        flag = True
      break
    j += 1
  if flag:
    print(ans)
    break

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
B = A[::-1]
l = 0
r = 10**6
def f(m):
  cnt = 0
  j = 0
  for i in range(N):
    while j<N:
      if A[i]+B[j]>=m:
        cnt += N-j
        break
      j += 1
  return cnt>=M
while l+1<r:
  n = (l+r)//2
  if f(n):
    l = n
  else:
    r = n
ans = 0
C = [0]
for i in range(N):
  C += [C[-1]+B[i]]
j = 0
m = 0
flag = False
for i in range(N):
  while j<N:
    if A[i]+B[j]>=l:
      x = min(N-j,M-m)
      ans += C[-1]-C[N-x]+A[i]*x
      m += x
      if m==M:
        flag = True
      break
    j += 1
  if flag:
    print(ans)
    break

Submission status: Wrong Answer

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


def f():
	welfare = 0
	ctr = 0
	while True:
		maximum_val = A.pop(0)
		welfare += maximum_val * 2
		ctr += 1
		if ctr == M:
			return welfare
		for a in A:
			for _ in range(2):
				welfare += maximum_val + a
				ctr += 1
				if ctr == M:
					return welfare
				
print(f())

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
# とけてない
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

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

ans = 0

def count(x):  # 和がx以上になる組み合わせの個数
	cnt = 0
	for y in A:  # 左手
		left = -(x-y)
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for y in A:
	if cnt == M:
		break
	left = -(l-y)
	idx = bisect(B, left)
	if cnt+idx >= M:
		idx = max(0, M-cnt)
		cnt = M
	else:
		cnt += idx
	ans += A_acc[idx]+idx*y

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
# とけてない
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

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

ans = 0

def count(x):  # 和がx以上になる組み合わせの個数
	cnt = 0
	for y in A:  # 左手
		left = -(x-y)
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for y in A:
	left = -(l-y)
	idx = bisect(B, left)
	if cnt+idx > M:
		idx = max(0, M-cnt)
		cnt = M
	else:
		cnt += idx
	ans += A_acc[idx]+idx*y

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
# とけてない
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

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

ans = 0

def count(x):  # 和がx以上になる組み合わせの個数
	cnt = 0
	for y in A:  # 左手
		left = -(x-y)
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for y in A:
	left = -(l-y)
	idx = bisect(B, left)
	if cnt+idx > M:
		idx = max(0, M-cnt)
	else:
		cnt += idx
	ans += A_acc[idx]+idx*y

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
# とけてない
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
A.sort(reverse=True)
B = [-x for x in A]

l = 0
r = 10**20+1

ans = 0

def count(x):  # 和がx以上になる組み合わせの個数
	cnt = 0
	for i in range(N):  # 左手
		left = -(x-A[i])
		cnt += bisect(B, left)

	return cnt

while l+1 != r:
	m = (l+r)//2
	if count(m) < M:
		r = m
	else:
		l = m
ans = 0

A_acc = list(accumulate([0]+sorted(A, reverse=True)))
cnt = 0
for i in range(N):
	left = -(l-A[i])
	idx = bisect(B, left)
	if cnt+idx > M:
		idx = M - cnt
	else:
		cnt += idx
	ans += A_acc[idx]+idx*A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=sorted(map(int,input().split()))
B=[0]
for a in A:
    B.append(B[-1]+a)
def f(n):
    a,b=0,0
    r=N-1
    for l in range(N):
        while r>-1 and A[l]+A[r]>=n:
            r-=1
        a+=N-1-r
        b+=A[l]*(N-1-r)+B[N]-B[r+1]
    return a,b
l,r=0,10**6
while l+1<r:
    t=(l+r)//2
    a,b=f(t)
    if a<=M:
        r=t
    else:
        l=t
print(b-t*(a-M))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=sorted(list(map(int,input().split())))

# M回の握手の幸福度最大化
# X以上になる握手を全て採用したときに、M通りを越える
# Xの最大値を求める

import bisect

ok=-1
ma=A[-1]
ng=(ma**2)+1

# x以上の握手をm通り以上作れるか
def isOk(x,m):
  cnt=0
  # 左手をループする
  for i in range(len(A)):
    left=A[i]
    minright=x-left
    # minright以上の数を数える
    cnt+=n-bisect.bisect_left(A,minright)
    if cnt>=m:
      return True
  return cnt>=m

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

x=ok
# x以上となる幸福度を足し合わせる
# 足し合わせた握手がMを越える場合、xぴったりを足し過ぎている

# 効率化のため累積和を作成
Asum=[0]+A
for i in range(1,len(Asum)):
  Asum[i]=Asum[i-1]+Asum[i]
  
# Aの添字i以降を全て足すときは、
# Asum[-1]-Asum[i]

ans=0
cnt=0
for i in range(len(A)):
  left=A[i]
  minright=x-left
  start=bisect.bisect_left(A,minright)
  cnt+=n-start
  ans+=left*(n-start)+(Asum[-1]-Asum[start])
  
if cnt>m:
  ans-=(cnt-m)*x
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = lr()
A.sort()

def check(x):
    # x以上のパワーの時握手すると全部で何回握手するのか返す
    ret = 0
    for a in A:
        y = x - a
        z = bisect_left(A, y)
        ret += N - z
    return ret

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

answer = 0
for a in A:
    i = bisect_left(A, left - a)
    answer += a * (N-i) + sum(A[i:])

print(answer)
# 32

Submission status: Wrong Answer

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

def handshake(a):
    return (a[0]*2+a[0]*(len(a)-1)*2) + sum(a[1:])*2

ans = 0
for i in range(n):
    combination = 1+ (len(a[i:])-1)*2
    if m > combination:
        ans += handshake(a[i:])
        m -= combination
    elif m == 0:
        break
    elif m < combination:
        if m == 1:
            ans += a[i:][0]*2
        else:
            q = (m-1)//2
            ans += a[i:][0]*2 + a[i:][0]*(m-1) + sum(a[i:][1:1+q])*2
            if (m-1)%2 == 1:
                ans += a[i:][1+q]               
        break
print(ans)

Submission status: Wrong Answer

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

def handshake(a):
    return (a[0]*2+a[0]*(len(a)-1)*2) + sum(a[1:])*2

ans = 0
total_combination = 0
for i in range(n):
    combination = 1+ (len(a[i:])-1)*2
    total_combination += combination
    if m > combination:
        ans += handshake(a[i:])
        m -= combination
    elif m == 0:
        break
    elif m < combination:
        if m == 1:
            ans += a[i:][0]*2
        else:
            q = (m-1)//2
            ans += a[i:][0]*2 + a[i:][0]*(m-1) + sum(a[i:][1:1+q])*2
            if (m-1)%2 == 1:
                ans += a[i:][1+q]               
        break
print(ans)

Submission status: Wrong Answer

Solution code:
count=0
res=0
M=0

class Node:
  def __init__(self, data):
    self.data=data
    self.left=None
    self.right=None

class BST:
  def __init__(self, number_list):
    self.root=None
    for node in number_list:
      self.insert(node)
  def insert(self, data):
    n=self.root
    if n==None:
      self.root=Node(data)
      return
    else:
      while True:
        entry=n.data
        if data < entry:
          if n.left is None:
            n.left=Node(data)
            return
          n=n.left
        elif data >= entry:
          if n.right is None:
            n.right=Node(data)
            return
          n=n.right
        else:
          n.data=data
          return
  def printTree(self,node):
    if node.left==None:
      print("N-",end="")
    else:
      print("%d-" %(node.left.data),end="")
    print(node.data,end="")
    if node.right==None:
      print("-N")
    else:
      print("-%d" %(node.right.data))
    if node.left!=None:
      self.printTree(node.left)
    if node.right!=None:
      self.printTree(node.right)
  def inorder(self,node):
    if node is not None:
      self.inorder(node.left)
      print(node.data)
      self.inorder(node.right)
  def order(self,node):
    global res
    global count
    global M
    if node is not None:
      self.order(node.right)
      res+=node.data
      count+=1
      if count==M:
        print(res)
        exit()
#      print(node.data)
      self.order(node.left)

args=input().split()
N=int(args[0])
M=int(args[1])
A=list(map(int,input().split()))
sumA=[]
for i in range(len(A)-1):
  for j in range(i,len(A)):
    if i==j:
      sumA.append(A[i]+A[j])
    else:
      sumA.append(A[i]+A[j])
      sumA.append(A[i]+A[j])
A=[]
tree=BST(sumA)
sumA=[]
tree.order(tree.root)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
comb_list = [ i+j for i in A for j in A]
comb_list = sorted(comb_list)
sum(comb_list[-M:])

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
comb_list = [ i+j for i in range(N) for j in range(N)]
comb_list = sorted(comb_list)
sum(comb_list[-M:])

Submission status: Wrong Answer

Solution code:
n,m = list(map(int,input().split()))
ai = list(map(int,input().split()))

ai = sorted(ai, reverse=True)


def score(ai, k):
    inx = 0
    s = 0
    while True:

        s += ai[0] + ai[int((inx -1 + 2)/2)]
        
        inx += 1
        k -=1
        if k <= 0:
            return s

        if inx >= (len(ai) -1) * 2 + 1:
            s += score(ai[1:], k)
            return s


print(score(ai,m))

Submission status: Wrong Answer

Solution code:
# REの原因を探るためのsubmission

import bisect

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

# ある値以上のAiがいくつあるかの情報を累積和で保持
num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


# for i in range(10**5-1, 0, -1):
#   num_A_or_more[i-1] += num_A_or_more[i]


# x以上となる手の組み合わせがM種類以上あるかどうかを判定
def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


# 2分探索でM種類以上の手の組み合わせがある満足度の最大値を求める
left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

# これがM種類以上の手の組み合わせがある満足度の最大値
x = left


# 降順に並べなおして累積和を求めておく
rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 # M種類を超えた場合は、一番小さくなる握手の組を最後に削る
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

Submission status: Wrong Answer

Solution code:
import itertools as iters

def main():
    N,M = [int(i) for i in input().rstrip().split(' ')]
    A = [int(i) for i in input().rstrip().split(' ')]
    S = [a+b for a in A for b in A]
    S = sorted(S,reverse=True)
    print(S)
    wel = 0
    for s in S:
        wel += s
        M -= 1
        #print(wel,s)
        if M <= 0:
            break
    print(wel)
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import bisect

n, m = map(int, input().split())
a = [int(item) for item in input().split()]
a.sort()
a_rev = sorted(a, reverse=True)

cumsum = [0]
for item in a:
    cumsum.append(cumsum[-1] + item)

# Use pair which sum goes over mid
l = 0; r = 10**10
while r - l > 1:
    mid = (l + r) // 2
    to_use = 0
    for i, item in enumerate(a_rev):
        useless = bisect.bisect_left(a, mid - item)
        to_use += n - useless
    if to_use >= m:
        l = mid
    else:
        r = mid
ans = 0
for i, item in enumerate(a_rev):
    useless = bisect.bisect_left(a, l - item)
    to_use = n - useless
    ans += item * to_use + cumsum[n] - cumsum[n - to_use]
print(ans)

Submission status: Wrong Answer

Solution code:
class FastModuloTransform():
    def __init__(self,omega=103,n=2**18,mod=2**18*5880+1):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega,mod-2,mod)
    def _bit_reverse_(self,d):
        n = len(d)
        ns = n>>1
        nss = ns>>1
        ns1 = ns+1
        i = 0
        for j in range(0,ns,2):
            if j<i:
                d[i],d[j] = d[j],d[i]
                d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1]
            d[i+1],d[j+ns] = d[j+ns],d[i+1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d
    def _fmt_(self,A,base):
        halfpow = pow(base,self.n//2,self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base,n,self.mod)
            wk = 1
            for j in range(m):
                for i in range(j,self.n,2*m):
                    U = A[i]
                    V = (A[i+m]*wk)%self.mod
                    A[i] = (U+V)%self.mod
                    A[i+m] = (U+V*halfpow)%self.mod
                wk = (wk*w)%self.mod
            m <<= 1
        return A
    def fmt(self,f):
        A = f+[0]*(self.n-len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A,self.omega)
        return F
    def ifmt(self,F):
        A = F+[0]*(self.n-len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n,self.mod-2,self.mod)
        f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)]
        return f
    def convolute(self,f,g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s*t)%self.mod for s,t in zip(F,G)]
        h = self.ifmt(H)
        return h

N,M = map(int,input().split())
power = list(map(int,input().split()))
count = [0 for _ in range(200010)]

for p in power:
    count[p] += 1

ntt = FastModuloTransform()
convoluted = ntt.convolute(count,count)

shake = 0
ans = 0

for i in range(len(convoluted))[::-1]:
    if shake + convoluted[i] <= M:
        ans += i*convoluted[i]
        shake += convoluted[i]
    else:
        ans += i*(M-shake)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
class FastModuloTransform():
    def __init__(self,omega=103,n=2**18,mod=2**18*5880+1):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega,mod-2,mod)
    def _bit_reverse_(self,d):
        n = len(d)
        ns = n>>1
        nss = ns>>1
        ns1 = ns+1
        i = 0
        for j in range(0,ns,2):
            if j<i:
                d[i],d[j] = d[j],d[i]
                d[i+ns1],d[j+ns1] = d[j+ns1],d[i+ns1]
            d[i+1],d[j+ns] = d[j+ns],d[i+1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d
    def _fmt_(self,A,base):
        halfpow = pow(base,self.n//2,self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base,n,self.mod)
            wk = 1
            for j in range(m):
                for i in range(j,self.n,2*m):
                    U = A[i]
                    V = (A[i+m]*wk)%self.mod
                    A[i] = (U+V)%self.mod
                    A[i+m] = (U+V*halfpow)%self.mod
                wk = (wk*w)%self.mod
            m <<= 1
        return A
    def fmt(self,f):
        A = f+[0]*(self.n-len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A,self.omega)
        return F
    def ifmt(self,F):
        A = F+[0]*(self.n-len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n,self.mod-2,self.mod)
        f = [(e*nrev)%self.mod for e in self._fmt_(A,self.rev)]
        return f
    def convolute(self,f,g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s*t)%self.mod for s,t in zip(F,G)]
        h = self.ifmt(H)
        return h

N,M = map(int,input().split())
power = list(map(int,input().split()))
count = [0 for _ in range(10**5+1)]

for p in power:
    count[p] += 1

ntt = FastModuloTransform()
convoluted = ntt.convolute(count,count)

shake = 0
ans = 0

for i in range(len(convoluted))[::-1]:
    if shake + convoluted[i] <= M:
        ans += i*convoluted[i]
        shake += convoluted[i]
    else:
        ans += i*(M-shake)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
def modinv(x, mod):
    a,b = x,mod
    u,v = 1,0
    while b:
        t = a//b
        a -= t*b; a,b = b,a
        u -= t*v; u,v = v,u
    return u%mod

def _garner(xs, mods):
    M = len(xs)
    coeffs = [1]*M
    constants = [0]*M
    for i in range(M-1):
        mod_i = mods[i]
        v = (xs[i] - constants[i]) * modinv(coeffs[i], mod_i) % mod_i
        for j in range(i+1,M):
            mod_j = mods[j]
            constants[j] = (constants[j] + coeffs[j] * v) % mod_j
            coeffs[j] = (coeffs[j] * mod_i) % mod_j

    return constants[-1]


def bit_reverse(d):
    n = len(d)
    ns = n>>1; nss = ns>>1
    ns1 = ns + 1
    i = 0
    for j in range(0, ns, 2):
        if j<i:
            d[i], d[j] = d[j], d[i]
            d[i+ns1], d[j+ns1] = d[j+ns1], d[i+ns1]
        d[i+1], d[j+ns] = d[j+ns], d[i+1]
        k = nss; i ^= k
        while k > i:
            k >>= 1; i ^= k
    return d

class NTT:
    def __init__(self, mod, primitive_root):
        self.mod = mod
        self.root = primitive_root

    def _ntt(self, a, sign):
        n = len(a)
        mod, g = self.mod, self.root
        tmp = (mod - 1) * modinv(n, mod) % mod # -1/n
        h = pow(g, tmp, mod) # ^n√g
        if sign < 0: h = modinv(h, mod)

        a = bit_reverse(a)

        m = 1
        while m < n:
            m2 = m<<1
            _base = pow(h, n//m2, mod)
            _w = 1
            for x in range(m):
                for s in range(x,n,m2):
                    u = a[s]
                    d = a[s+m]* _w % mod
                    a[s] = (u+d)%mod
                    a[s+m] = (u-d)%mod
                _w = _w * _base % mod
            m <<= 1
        return a

    def ntt(self, a):
        return self._ntt(a,1)

    def intt(self, a):
        mod = self.mod
        n = len(a)
        n_inv = modinv(n, mod)
        a = self._ntt(a,-1)
        for i in range(n):
            a[i] = a[i]*n_inv%mod
        return a

    def convolution(self, a, b):
        mod = self.mod
        ret_size = len(a)+len(b)-1
        n = 1 << (ret_size-1).bit_length()
        _a = a + [0] * (n - len(a))
        _b = b + [0] * (n - len(b))
        _a = self.ntt(_a)
        _b = self.ntt(_b)
        _a = [x*y%mod for x,y in zip(_a,_b)]
        _a = self.intt(_a)
        _a = _a[:ret_size]
        return _a


def convolution_ntt(a, b):
    mods = (1224736769,)
    ntt1 = NTT(mods[0], 3)
    x1 = ntt1.convolution(a, b)
    return x1

m,k = map(int,input().split())
f = list(map(int,input().split()))
n = max(f)+1
g = [0]*n
for x in f: g[x] += 1
h = convolution_ntt(g,g)
ans = 0
cnt = 0
for i in range(len(h)-1,-1,-1):
  if cnt + h[i] < k:
    ans += h[i]*i
    cnt += h[i]
  else:
    ans += (k-cnt)*i
    break
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)>m:
    lx += 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx += 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
B = [0]*(10**5)
for i in A:
    B[i-1]+=1
    
C = convolve(B,B)
 
m = 0
ans = 0
now = 2*10**5
while m < M and now>1:
    if C[now-2] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now-2]
        m += C[now-2]
        now -= 1
        
        
if N**2==M:
    print(2*N*sum(A))
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 1107296257, 5
    n0, n1 = len(a), len(b)
    n = 1 << (n0+n1 - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0+n1-1)]
  
N,M = map(int,input().split())
A = list(map(int,input().split()))
 
B = [0]*(10**5)
for i in A:
    B[i-1]+=1
    
C = convolve(B,B)
 
m = 0
ans = 0
now = 2*10**5
while m < M and now>1:
    if C[now-2] >= M-m:
        ans += now*(M-m)
        break
    else:
        ans += now*C[now-2]
        m += C[now-2]
        now -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate

def func(x):
    cnt = 0
    for i in a:
        index = bisect.bisect_left(a, x - i)
        cnt += N - index
    if cnt >= M:
        return True
    else:
        return False

N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ar = sorted(a, reverse=True)
b = [0] + list(accumulate(ar))
print(ar)
print(b)
MIN = 0
MAX = 2 * 10 ** 5 + 1
while MAX - MIN > 1:
    MID = (MIN + MAX) // 2
    if func(MID):
        MIN = MID
    else:
        MAX = MID

ans = 0
cnt = 0
for i in ar:
    index = bisect.bisect_left(a, MIN - i)
    ans += i * (N - index) + b[N - index]
    cnt += N - index
print(ans - (cnt - M) * MIN)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
scores = sorted(map(int, input().split()), reverse=True)
results = []

def suggest_for(i):
	if i>=n:
		return
	x = scores[i]
	results.append(x+x)
	for j, y in enumerate(scores[i+1 : min(n, int(m/2+0.5))]):
		results.append(x+y)
		results.append(x+y)
	

for i in range(0, m):
	suggest_for(i)

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

Submission status: Wrong Answer

Solution code:
import heapq
N,M=map(int,input().split())
A=sorted([int(i) for i in input().split()],reverse=True)
q=[]
heapq.heappush(q,(-A[0]-A[0],0,0))
ans=0
for k in range(M):
    s,i,j=heapq.heappop(q);s=-s
    ans+=s
    if i<N-1:
        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(ans)