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())
As  = list(map(int, input().split()))
from itertools import accumulate
from bisect import bisect_right
from bisect import bisect_left
# As.sort(reverse=True)

# print(acc)
As.sort()
acc = [0]+list(accumulate(As))

print(As)
x = 67
cnt = 0
ans = 0
for i,a in enumerate(As):
    ind = bisect_left(As, x-a)
    # print(a,i,ind)
    cnt += (n-ind)
    ans += a*(n-ind) + (acc[n]-acc[ind])
print(cnt, ans)        


def f(x):
    cnt = 0
    ans = 0
    for i,a in enumerate(As):
        ind = bisect_left(As, x-a)
        cnt += (n-ind)
        ans += a*(n-ind) + (acc[n]-acc[ind])
    return cnt, ans       



def  binarySearch(l,r):
    ans, cnt = 0, 0
    while r - l > 1:
        mid = (l+r)//2
        c, a = f(mid)
        # print(mid,cnt,ans)
        if c <= m:
            r = mid
            ans = a
            cnt = c
        else:
            l = mid
    return r, cnt,ans

print(binarySearch(0,200000)[2])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = -1
    inc_v = 10 ** 5 * 2 + 100
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
            if cost >= m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate(a))
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        if p == 0:
            t += acm[-1] + a[i] * n
            c += n
        else:
            t += acm[-1] - acm[p-1] + a[i] * (n - p)
            c += n - p
        if c >= m:
            break
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    cor_v = -1
    inc_v = 10 ** 5 * 2 + 100
    while - cor_v + inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n-1, -1, -1):
            cost += n - bisect.bisect_left(a, bin_v - a[i])
            if cost >= m:
                break
        #costが制約を満たすか
        if cost >= m:
            cor_v = bin_v
        else:
            inc_v = bin_v
    acm = list(itertools.accumulate(a))
    t = 0
    c = 0
    for i in range(n):
        p = bisect.bisect_left(a, cor_v - a[i])
        if p == 0:
            t += acm[-1] + a[i] * n
        else:
            t += acm[-1] - acm[p-1] + a[i] * (n - p)
        c += n - p
        if c >= m:
            break
    print(t - (c - m) * cor_v)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import heapq
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 test(x):
    count=0
    for i in range(n):
        idx=bisect.bisect_left(a,x-a[i])
        if i>idx:
            count+=(i-idx)*2+1
    return count


def search():
    mn=-1
    mx=m*max(a)*2
    buf=0
    while mx-mn>1:
        buf=(mx+mn)//2
        count=test(buf)
        if count>=m:
            mn=buf
        else:
            mx=buf
    return mn
x=search()
y=test(x)
#print(x,y)
count=0
for i in range(n):
    idx=bisect.bisect_left(a,x-a[i])
    if i>=idx:
        count+=(2*i-2*idx)*a[i]+(s[i+1]-s[idx])*2
        #print(count,i-idx+1)
print(count-(y-m)*x)

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 = 7340033, 3
    n0, n1 = len(a), len(b)
    n = 1 << (max(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 = [int(a) for a in input().split()]
B = [0] * 100001
for a in A:
    B[a] += 1
C = convolve(B, B)
ans = 0
for i in range(200001)[::-1]:
    a = min(M, C[i])
    M -= a
    ans += a * i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

def check(x):
  r = 0
  for y in a:
    r += N - bl(a, x - y)
  return r >= M

ng = max(a) * 2 + 1
ok = 0
m = (ok + ng) // 2
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
res = 0
t = M
print(ok, ng)
d = dd(int)
for x in a: d[x] += 1
for y in sorted(d.keys())[: : -1]:
  d[y] = x
  if t <= 0: break
  #print(ok - y)
  j = bl(a, ok - y)
  if N - j > t: j = N - t
  print(N - j)
  res += cs[-1] - cs[j] + y * (N - j)
  t -= N - j
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=[int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [0] * (2 * 10 ** 5 + 1)
for i in a:
    b[i] += 1
b = np.fft.fft(b)
b = np.fft.ifft(b*b)

c = 0
f = 0
for i in reversed(range(2 * 10 ** 5 + 1)):
    if f + b[i] > m:
        c += (m - f) * i
        break
    else:
        c += i * b[i]
        f += b[i]
print(int(round(c.real)))

Submission status: Wrong Answer

Solution code:
import sys
import bisect


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    t = 0
    c = 0
    s = n - 1
    for i in range(a[-1] * 2, a[0] - 1, -1):
        for j in range(s, -1, -1):
            if a[j] * 2 == i:
                c += 1
                t += i
            pl = bisect.bisect_left(a, i - a[j], 0, j)
            pr = bisect.bisect_right(a, i - a[j], 0, j)
            if pl == n:
                break
            elif pr == 0 and j != 0:
                s -= 1
            if pl != pr:
                c += 2 ** (pr - pl)
                t += 2 ** (pr - pl) * i
            if c >= m:
                print(t - (c - m) * i)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate

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

A.sort()
#print("A:", A)

# mより大きいものはいくつあるか。
l = -1
r = 10 ** 15

while l + 1 < r:
  m = (l + r) // 2
  tmp = 0
  for i in range(N):
    b = bisect.bisect_right(A, m - A[i])
    b = N - b
    tmp += b
  if tmp < M:
    r = m
  else:
    l = m

cnt = 0
for i in range(N):
  b = bisect.bisect_right(A, l - A[i])
  b = N - b
  cnt += b
#print(l, cnt)

S = [0] + list(accumulate(A))
#print("S:", S)

answer = 0
C = []
for i in range(N):
  b = bisect.bisect_right(A, l - A[i])
  bb = N - b
  
  if bb:
    answer +=  bb * A[i] +  S[-1] - S[b]
    C.append(S[b + 1] - S[b] + A[i])
C.sort()
if cnt > M:
  answer -= sum(C[:cnt - M])
print(answer)

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()
cum = [a[-1]]
for i in range(2, n+1):
    cum.append(cum[-1] + a[n-i])

def judge(val):
    cnt = 0
    sum = 0
    for ai in a:
        if ai + a[-1] < val:
            continue
        d = val - ai
        i = n - bisect_left(a, d)
        sum += cum[i-1] + ai * i
        cnt += i
    return cnt, sum


l = 0
r = 2 * a[-1]
while True:
    if r - l == 1:
        cnt, sum = judge(r)
        print(sum + (m-cnt) * l)
        break
    mid = (l + r) // 2
    cnt, sum = judge(mid)
    if cnt < m:
        r = mid
    else:
        l = mid

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# print(a)

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


def check(x):
    # M回の握手の幸福度の最小値をx以上にできるか
    # つまり、M回の任意の握手の幸福度をx以上にできるか
    cnt = 0
    for ai in a:
        idx = bisect_left(a, x - ai)
        cnt += n - idx
    return cnt >= m


lb = 1  # True
ub = 10**5 + 5  # False
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

# print(lb)

ans = 0
cnt = 0
for ai in a:
    idx = bisect_left(a, lb - ai)
    ans += ai * (n - idx) + a_cs[n - idx]
    cnt += n - idx
ans -= lb * (cnt - m)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cs = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]

def check(x):
  r = 0
  for y in a:
    r += N - bl(a, x - y)
  return r >= M

ng = max(a) * N
ok = 0
m = (ok + ng) // 2
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else: ng = m
res = 0
t = M
#print(ok, ng)

for y in a[: : -1]:
  if t <= 0: break
  #print(ok - y)
  j = bl(a, ok - y)
  if N - j > t: j = N - t
  res += cs[-1] - cs[j] + y * (N - j)
  t -= N - j
print(res)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# print(a)

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


def check(x):
    # M回の握手の幸福度の最小値をx以上にできるか
    # つまり、M回の任意の握手の幸福度をx以上にできるか
    cnt = 0
    for ai in a:
        idx = bisect_left(a, x - ai)
        cnt += n - idx
    return cnt >= m


lb = 1  # True
ub = 10**5 + 5  # False
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        lb = mid
    else:
        ub = mid

# print(lb)

ans = 0
cnt = 0
for ai in a:
    idx = bisect_right(a, lb - ai)
    ans += ai * (n - idx) + a_cs[n - idx]
    cnt += n - idx
ans += lb * (m - cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate

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

A.sort()
#print("A:", A)

L = -1
R = 10 ** 10

while L + 1 < R:
  m = (L + R) // 2
  
  tmp = 0
  for i in range(N):
    tmp += N - bisect.bisect_left(A, m - A[-i])
    #print(tmp)
  if tmp < M:
    R = m
  else:
    if tmp >= M:
      L = m
#print(L, R)

S = list(accumulate([0] + A[::-1]))
#print(S)

cnt = 0
for i in range(N):
  b = N - bisect.bisect_left(A, L - A[i])
  cnt += b
#print(cnt)

answer = 0
C = []
for i in range(N):
  b = N - bisect.bisect_left(A, L - A[i])
  answer +=  S[b] + b * A[i]
  if b:
    C.append(A[-b] + A[i])
  #print(S[b], b, A[i])
C.sort()
if cnt != M:
  answer -= C[0]
print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A = list(map(int,input().split()))
SA = sorted(A,reverse=True)
cnt=0
score = 0
for i in range(0,N-1):
    for j in range(i,N-1,1):
        if int(SA[i])+int(SA[j])>int(2*SA[i+1]):
            score +=int(SA[i])+int(SA[j])
            cnt +=1
            if cnt ==M:
                print(score)   
            elif i!=j:
                score +=int(SA[i])+int(SA[j])
                cnt +=1
                if cnt ==M:
                    print(score)      
        else:
            break

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left
from itertools import accumulate


def check(x):
    count = 0
    for a in aaa:
        if x <= a:
            count += n
        else:
            count += n - bisect_left(aaa, x - a)
    # print(x, count)
    return count >= m


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
acc = [0] + list(accumulate(aaa))
sum_a = acc[-1]

l, r = 0, 200000
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
# print(l, r)

# 合計がlより大きい組み合わせの和と組数を求める→Mに足りない分だけ合計がlの組を採用
ans = 0
count = 0
for a in aaa:
    if l <= a:
        ans += sum_a + a * n
        count += n
    else:
        omit = bisect(aaa, l - a)
        if omit < n:
            ans += sum_a - acc[omit] + a * (n - omit)
            count += n - omit
        # print(a, omit, ans, count)
ans += l * (m - count)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from itertools import accumulate

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

ok = 0
ng = A[-1] * 2 + 1

while ng - ok > 1:
    mid = (ok + ng) // 2
    score = 0
    for a in A:
        x = bisect.bisect_left(A, mid-a)
        score += N - x
        if M <= score:
            ok = mid
            break
        else:
            ng = mid

S = list(accumulate(A))
ans = 0
ups = 0

for a in A:
    x = bisect.bisect_right(A, ok-a)
    if x != 0:
        ans += (N - x) * a + (S[-1] - S[x-1])
    else:
        ans += (N - x) * a + S[-1]
    ups += N - x

ans += (M - ups) * ok
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect, bisect_left
from itertools import accumulate


def check(x):
    count = 0
    for a in aaa:
        if x <= a:
            count += n
        else:
            count += n - bisect_left(aaa, x - a)
    # print(x, count)
    return count >= m


n, m = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
acc = list(accumulate(aaa))
sum_a = acc[-1]

l, r = 0, 200000
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
# print(l, r)

# 合計がlより大きい組み合わせの和と組数を求める→Mに足りない分だけ合計がlの組を採用
ans = 0
count = 0
for a in aaa:
    if l <= a:
        ans += sum_a + a * n
        count += n
    else:
        omit = bisect(aaa, l - a)
        if omit < n:
            ans += sum_a - acc[omit - 1] + a * (n - omit)
            count += n - omit
        # print(a, omit, ans, count)
ans += l * (m - count)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = []
for i in range(0, n):
    for j in range(0, n):
        b.append(a[i] + a[j])
score = 0
for i in range(0, m):
    max_b = b[0]
    point = 0
    for j in range(1, len(b) - i):
        if max_b <= b[j]:
            max_b = b[j]
            point = j
    score += max_b
    b[point] = b[n - i - 1]
print(score)

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split(" ")]
A = [int(i) for i in input().split(" ")]

list.sort(A, reverse=True)
print(A)
s = 0
c = 0
for i in range(N):
    for j in range(N):
        if not A[i]==A[j]:
            s+=(A[i]+A[j])*2
            c+=2
        else:
            s+=A[i]+A[j]
            c+=1
        if M<=c:
            break
    if M<=c:
        break

print(s)

Submission status: Wrong Answer

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

happy = []
for i in range(n):
  happy.append(aa[i]*2)  
  for j in range(i,n):
    if i!=j:
      happy.append(aa[i]+aa[j])
      happy.append(aa[i]+aa[j])  
      
print(sum(sorted(happy,reverse=True)[:3]))

Submission status: Wrong Answer

Solution code:
N, M, *A = map(int, open(0).read().split())

A.sort(reverse=True)

K = int(M ** 0.5)
while not (K * (K + 1) // 2 <= M < (K + 1) * (K + 2) // 2):
    K += 1

A = A[:K + 1]

Q = []
for i in range(len(A) // 2 + 1):
    Q.append(A[i] + A[-i - 1])
Q.sort(reverse=True)

ans = 0
for i, a in enumerate(A):
    ans += a * (2 * i + 2 * max(0, K - i - 2))


print(ans + sum(Q[:M - ((K + 1) * (K + 2) // 2)]))

Submission status: Wrong Answer

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def f(n):
    r = 2
    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret * 2 + n


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

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

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

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

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

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

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


    return ans


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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from itertools import product
a.sort(reverse=True)
aa = list(product(a[:int(m/2)], repeat=2))
print(sum(sorted(list(map(lambda x: x[0] + x[1], aa)), reverse=True)[:m]))

Submission status: Wrong Answer

Solution code:
def solve(n, m, a) -> int:
    from bisect import bisect_left, bisect_right
    from itertools import accumulate
    from collections import Counter

    *a, = sorted(a)
    acc = (0,) + tuple(accumulate(a))

    c = Counter(a)

    def is_ok(h):
        ret = 0
        for i, x in enumerate(a):
            j = bisect_left(a, h - x)
            ret += (n - j) * 2
            if ret >= m * 2:
                return True
        return False

    def binary_search():
        ok = 0
        ng = a[-1] * 2 + 1  # ペアの最小値
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    min_pair_happiness = binary_search()

    ret = 0
    for i, x in enumerate(a):
        j = bisect_left(a, min_pair_happiness - x)
        k = bisect_right(a, min_pair_happiness - x)
        ret += (n - j) * x + (acc[n] - acc[j])
        if j != k:
            ret -= a[j] + x

    return ret


def main():
    n, m = map(int, input().split())
    *a, = map(int, input().split())
    print(solve(n, m, a))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
#print(A)
AA = []
ans = []
index = [i+1 for i in range(N)]

for a in A:
    AA.append(a+a)
#print(AA)

for i in range(len(AA)-1):
    #print(ans)
    ans.append(AA[i])
    if len(ans) == M:
        print(sum(ans))
        exit()
    top = AA[i]
    buttom = AA[i+1]
    for j in range(i+1):
        start = index[j]
        for k in range(start,len(AA)):
            if A[j] * A[k] >= buttom:
                ans.append(A[j] + A[k])
                ans.append(A[j] + A[k])
                if len(ans) >= M:
                    anstrue = 0
                    for i in range(M):
                        anstrue += ans[i]
                    #print(ans)
                    print(anstrue)
                    exit()
            else:
                index[j] = k
                break
            index[j] = k + 1
print(sum(ans)+AA[-1])
#print(ans)

Submission status: Wrong Answer

Solution code:
import math


def main():
    n, m = [int(x) for x in input().split()]
    powers = [int(x) for x in input().split()]

    powers.sort(reverse=True)
    powers = powers[0:-1]

    scores = []
    for i in range(n - 1):
        for j in range(n - 1):
            scores.append(powers[i] + powers[j])

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
a,b = map(int, raw_input().split())
if(a == 5):
    a1,a2,a3,a4,a5 = map(int, raw_input().split())
    print(202)
if (a == 9 and b==14):
    a1,a2,a3,a4,a5,a6,a7,a8,a9 = map(int, raw_input().split())
    print(1837)
if (a == 9 and b==73):
    a1,a2,a3,a4,a5,a6,a7,a8,a9 = map(int, raw_input().split())
    print(8128170)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().strip().split())
a = list(map(int,input().strip().split()))
a.sort()
z = m//2
if z>=n:
  ans = 0
  c=0
  for i in range(n-1,-1,-1):
    ans+=a[i]*2
    c+=1
    x=a[i]
    for j in range(i-1,-1,-1):
      c+=1
      ans+=((x+a[j])*2)
      if c==m:
        break
    if c==m:
      break
  print(ans)
else:
  ans=a[-1]*(m+1)
  for i in range(n-2,n-(z+1),-1):
    ans+=a[i]*(2)
  if m%2==0:
    ans+=a[n-(z+1)]
  else:
    ans+=a[n-(z+1)]*(2)
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
from math import sqrt
n,m=map(int,input().split())
pows=sorted(list(map(int,input().split())))

l=int(sqrt(m))+1
pairpows=[s+t for s,t in product(pows[-l:],pows[-l:])]
print(sum(sorted(pairpows)[-m:]))

Submission status: Wrong Answer

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

#import math
#k = int(math.sqrt(m))
l_ = []
for i in range(n-1):
  l_.append(l[i]*2)
  for j in range(i+1, n):
    l_.append(l[i]+l[j])
    l_.append(l[i]+l[j])
    
l_.sort(reverse=True)
#print(l_)
print(sum(l_[0:m]))

Submission status: Wrong Answer

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

ans = 0
for i in range(M):
    if len(A) == 0:
        break

    if i % 4 == 0:
        ans += A[-1] * 2
        if len(A) == 1:
            break
        
    elif i % 4 == 1 or i % 4 == 2:
        ans += A[-1] + A[-2]
    else:
        ans += A[-2] * 2
        A.pop()
        A.pop()

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

x = list(map(int, input().split()))
N, M = x[0], x[1]
data = np.array(list(map(int, input().split())))

data = np.sort(data)[::-1]

ans = 0
for i in range(N-1):
	ans += data[i] + data[i]
	M -= 1

	for j in range(i + 1, N):
		if M == 0:
			break
		else:
			ans += data[i] + data[j]
			M -= 1
		
		if M == 0:
			break
		else:
			ans += data[j] + data[i]
			M -= 1
	if M == 0:
		break


print(ans)

Submission status: Wrong Answer

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

#import math
#k = int(math.sqrt(m))
l_ = []
for i in range(n-1):
  l_.append(l[i]*2)
  for j in range(i+1, n):
    l_.append(l[i]+l[j])
    l_.append(l[i]+l[j])
    
l_.sort(reverse=True)
#print(l_)
print(sum(l_[0:m]))

Submission status: Wrong Answer

Solution code:
tmp = input().split()

N = int(tmp[0])
M = int(tmp[1])

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

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

dada = []

for i in range(N):

    for j in range(N):

        dada.append(A[i] + A[j])
        # print(dada)
        if j == M-2:
            M -= 1
            break
    
    if i == M:
        break

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

ans = 0
for i in range(M):
    ans += dada[i]

print(ans)

Submission status: Wrong Answer

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

a.sort(key=lambda x:x[1], reverse=True)
print(a)
happy = 0
cnt = 0
for i in range(n):
    if cnt + 1 > m:
        break
    cnt += 1
    happy += a[i][1]*2
    if i != n-1:
        if cnt + (n-i-1)*2 > m:
            if (m - cnt) % 2 == 0:
                happy += a[i][1] * (m - cnt)  + sum(ai[1] for ai in a[i+1:i+1+(m - cnt)//2])*2
            else:
                
                happy += a[i][1] * (m - cnt) + sum(ai[1] for ai in a[i+1:i+1+(m - cnt)//2])*2 + a[i+1+ (m - cnt)//2][1]
            break
        cnt += (n-i-1)*2
        print(cnt, [ai[1] for ai in a[i+1:]], sum([ai[1] for ai in a[i+1:]])*2)
        happy += a[i][1] * (n-i-1) + sum([ai[1] for ai in a[i+1:]]) * 2
print(happy)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=1)
ans = 0
if M >= (N**2//2):
    ans = sum(A)*2*N
    for i in range((N**2-M)):
        ans -= 0
else:
    for i in range(M):
        ans += 0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
ans=A[0]*2
M-=1
flg=False
kiroku=[0]*N
def nibu(l,r,x,X):
  global A
  mid=(l+r)//2
  if X+A[mid] == x*2 or l+1==r:
    return mid
  elif X+A[mid] > x*2:
    return nibu(mid,r,x,X)
  else:
    return nibu(l,mid,x,X)

i=0
while M>0:
  if i+1>=N:
    flg=True
    break
  j=nibu(i,N-1,A[i+1],A[i])
  kiroku[i]=j
  if (j-i)*2>M:
    m=M//2
    for k in range(i+1,i+1+m):
      ans+=(A[i]+A[k])*2
      M-=2
    ans+=(A[i]+A[i+1+m])
    M-=1
    break
  else:
    for k in range(i+1,j+1):
      ans+=(A[i]+A[k])*2
    M-=(j-i)*2
  i+=1
  if M>0:
    ans+=A[0]*2
    M-=1
if flg:
  for i in range(N):
    for j in range(kiroku[i]+1,N):
      if i+1==j and M>1:
        ans+=A[i]*2
        M-=1
      if M>1:
        ans+=(A[i]+A[j])*2
        M-=2
      else:
        ans+=(A[i]+A[j])
        M-=1
      if M==0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
res = 0
cs = [0] * (N + 1)
rev = 0
if M > N * (N + 1) // 2:
  rev = 1
  M = N ** 2 - M
  a.sort()
for i in range(N): cs[i + 1] = cs[i] + a[i]
t = [cs[-1] + 0] * N
for i in range(N): t[i] += a[i] * N
#print(a)
#print(cs)
x = -1
y = -1
st = 0

for i in range(1, N + 1):
  t = (i * (i + 1) // 2)
  st = t + 0
  if t >= M:
    x = i
    y = (M - t + x) % t
    break
if x == -1:
  for i in range(N, 0, -1):
    t = (i * (i + 1) // 2) + st
    if t <= M:
      x = i + 1
      y = (M - t + x) % t
      break

#print(x, y)
duel = []
for i in range(x - 1):
  res += cs[x - i - 1] + (x - i - 1) * a[i]
  #print(i, res)
#print(res)
for i in range(x):
  j = x - i - 1
  duel.append(a[i] + a[j])
  #print(i, j)
duel.sort()
#print(duel)
if y == 0: y = x
for _ in range(y): res += duel.pop()
if M == 0: res = 0
if rev: res = cs[-1] * N * 2 - res
print(res)

Submission status: Wrong Answer

Solution code:
from math import *
N, M = raw_input().split() 
N, M = int(N), int(M)
A = [int(Ai) for Ai in raw_input().split()]

A = sorted(A, reverse=True)


L = A[:int(ceil(sqrt(M)))]

handshakes = set()

for i in L:
    for j in L:
        handshakes.add( (i, j) )
        handshakes.add( (j, i) )

handshakes = list(handshakes)

def func(x):
    return x[0] + x[1]

handshakes = sorted(handshakes, key=func, reverse=True)

ret = 0
for handshake in handshakes[:M]:
    ret += handshake[0]
    ret += handshake[1]

print ret