# PPaste!

### problem setter's code

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 #py2 n = input() k = input() assert 1 <= n <= 10**5 assert 1 <= k <= n lis = [] for i in range(n): lis.append(input()) lis.sort() sum_lis = [] for i in lis: assert 0 <= i <= 10**9 val = 1-k answer = 0 sum_lis.append(lis[0]) for i in range(1,n): sum_lis.append(sum_lis[i-1]+lis[i]) for i in range(k): answer += val*lis[i] val += 2 final_answer = answer for i in range(k,n): new_answer = answer + (k-1)*lis[i] + (k-1)*lis[i-k] - 2*(sum_lis[i-1]-sum_lis[i-k]) final_answer = min(new_answer, final_answer) answer = new_answer print final_answer =============================== #C++ #include #include #include #include using namespace std; #define Max_N 100001 typedef long long int ll; long long int sum[Max_N]; int N,K,input[Max_N]; ll min(ll a,ll b) { if(a>b) return b; else return a; } int main() { int val; scanf("%d%d",&N,&K); assert(1<=N && N<=100000); assert(1<=K && K<=N); for(int i=1;i<=N;i++) { scanf("%d",&input[i]); assert(0<=input[i] && input[i]<=1000000000); } input[0]=0; sort(input+1,input+N+1); sum[0]=0; for(int i=1;i<=N;i++) sum[i]=input[i]+sum[i-1]; val=1-K; ll answer=0,compare,previous; for(int i=1;i<=K;i++){ answer+=(ll)val*input[i]; val+=2; } //printf("%lld is answeer\n",answer); previous=answer; for(int i=K+1;i<=N;i++){ compare=(ll)(K-1)*input[i]; compare=previous + (ll)(K-1)*input[i] + (ll)(K-1)*input[i-K]-(ll)2*(sum[i-1]-sum[i-K]); answer=min(answer,compare); previous=compare; } printf("%lld\n",answer); return 0; }