Submission #9455922


Source Code Expand

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

import numpy as np

N,K = map(int,readline().split())
A = np.array(read().split(),np.int64)
MOD = 10 ** 9 + 7

def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv

fact, fact_inv = make_fact(10 ** 5 + 100)

A.sort()
coef = (fact[K-1:N] * fact_inv[K-1] % MOD * fact_inv[0:N-K+1] % MOD)[::-1]

answer = ((A[::-1][:N-K+1] - A[:N-K+1]) * coef % MOD).sum() % MOD
print(answer)

Submission Info

Submission Time
Task E - Max-Min Sums
User maspy
Language Python (3.4.3)
Score 500
Code Size 986 Byte
Status AC
Exec Time 312 ms
Memory 24752 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 18
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All max_01, max_02, max_03, max_04, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
max_01 AC 312 ms 24752 KB
max_02 AC 191 ms 18564 KB
max_03 AC 191 ms 18564 KB
max_04 AC 192 ms 18520 KB
random_01 AC 185 ms 17244 KB
random_02 AC 169 ms 16500 KB
random_03 AC 192 ms 18644 KB
random_04 AC 191 ms 18560 KB
random_05 AC 183 ms 17360 KB
random_06 AC 168 ms 16456 KB
random_07 AC 167 ms 16456 KB
random_08 AC 167 ms 16372 KB
random_09 AC 178 ms 17156 KB
random_10 AC 170 ms 16652 KB
sample_01 AC 166 ms 16328 KB
sample_02 AC 167 ms 16328 KB
sample_03 AC 166 ms 16372 KB
sample_04 AC 165 ms 16328 KB