Submission #9219994


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 価値 x 以上の握手を全て行うとする
# 握手回数が決まる。左手ごとに集計できる。

import numpy as np

N,M = map(int,readline().split())
A = np.array(read().split(),np.int64)

A.sort()

def shake_cnt(x):
    # x 以上の握手を全て行うとして、握手の回数を数える
    # 行わない握手を数える
    X = np.searchsorted(A,x-A)
    return N * N - X.sum()

left = 0 # 握手の回数がM以上
right = 10 ** 6 # 握手の回数がM未満
while left + 1 < right:
    x = (left + right) // 2
    if shake_cnt(x) >= M:
        left = x
    else:
        right = x

left,right

# right 以上の握手を全て行ったとして、回数と総和を計算

X = np.searchsorted(A,right-A) # 行わない人数
Acum = np.zeros(N+1,np.int64) # 人数 -> 累積和
Acum[1:] = np.cumsum(A)

shake = N * N - X.sum()
happy = (Acum[-1] - Acum[X]).sum() + (A * (N - X)).sum()

happy += (M - shake) *left
print(happy)

Submission Info

Submission Time
Task E - Handshake
User maspy
Language Python (3.4.3)
Score 500
Code Size 1115 Byte
Status AC
Exec Time 323 ms
Memory 18236 KB

Judge Result

Set Name Sample All after_contest
Score / Max Score 0 / 0 500 / 500 0 / 0
Status
AC × 3
AC × 66
AC
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 100.txt, 101.txt, 102.txt, 103.txt, 104.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, s1.txt, s2.txt, s3.txt
after_contest
Case Name Status Exec Time Memory
01.txt AC 151 ms 12448 KB
02.txt AC 149 ms 12404 KB
03.txt AC 149 ms 12404 KB
06.txt AC 148 ms 12448 KB
07.txt AC 280 ms 16880 KB
08.txt AC 218 ms 14824 KB
09.txt AC 244 ms 15172 KB
10.txt AC 166 ms 12968 KB
100.txt AC 150 ms 12280 KB
101.txt AC 149 ms 12404 KB
102.txt AC 149 ms 12448 KB
103.txt AC 148 ms 12448 KB
104.txt AC 149 ms 12404 KB
11.txt AC 267 ms 16752 KB
12.txt AC 186 ms 13544 KB
13.txt AC 293 ms 18088 KB
14.txt AC 299 ms 17336 KB
15.txt AC 293 ms 17288 KB
16.txt AC 293 ms 17296 KB
17.txt AC 294 ms 17244 KB
18.txt AC 311 ms 17964 KB
19.txt AC 278 ms 17304 KB
20.txt AC 290 ms 17512 KB
21.txt AC 310 ms 18012 KB
22.txt AC 288 ms 17400 KB
23.txt AC 293 ms 17288 KB
24.txt AC 282 ms 16976 KB
25.txt AC 276 ms 18008 KB
26.txt AC 290 ms 17100 KB
27.txt AC 323 ms 17400 KB
28.txt AC 289 ms 17324 KB
29.txt AC 278 ms 16976 KB
30.txt AC 300 ms 17492 KB
31.txt AC 267 ms 17628 KB
32.txt AC 270 ms 17216 KB
33.txt AC 266 ms 17584 KB
34.txt AC 268 ms 17352 KB
35.txt AC 268 ms 17576 KB
36.txt AC 268 ms 17620 KB
37.txt AC 269 ms 17960 KB
38.txt AC 271 ms 17996 KB
39.txt AC 271 ms 17288 KB
40.txt AC 268 ms 18000 KB
41.txt AC 271 ms 17176 KB
42.txt AC 275 ms 17272 KB
43.txt AC 266 ms 16960 KB
44.txt AC 273 ms 17168 KB
45.txt AC 267 ms 17464 KB
46.txt AC 266 ms 17004 KB
47.txt AC 267 ms 17080 KB
48.txt AC 267 ms 17500 KB
49.txt AC 275 ms 17220 KB
50.txt AC 272 ms 17720 KB
51.txt AC 271 ms 17836 KB
52.txt AC 268 ms 17720 KB
53.txt AC 271 ms 16960 KB
54.txt AC 273 ms 17784 KB
55.txt AC 321 ms 18088 KB
56.txt AC 270 ms 17448 KB
57.txt AC 280 ms 17488 KB
58.txt AC 261 ms 16212 KB
59.txt AC 275 ms 17552 KB
60.txt AC 269 ms 18236 KB
s1.txt AC 149 ms 12404 KB
s2.txt AC 148 ms 12404 KB
s3.txt AC 148 ms 12448 KB