/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A=(A_1,A_2,\cdots,A_N) があります． 以降この問題では，A の先頭 K 項の和を スコア と呼ぶことにします． また，入力で与えられた A のスコアを s と置くことにします．
あなたは，以下の操作を好きな回数繰り返すことができます．
- A のある隣接する 2 要素を選び，それらの値を入れ替える．
あなたの目標は，スコアを s+1 以上にすることです． 目標が達成可能であるかどうか判定し，また可能であるなら必要な最小の操作回数を求めてください．
制約
- 2 \leq N \leq 4 \times 10^5
- 1 \leq K \leq N-1
- 1 \leq A_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 \cdots A_N
出力
目標が達成可能でない場合，-1 を出力せよ．
可能である場合，必要な最小の操作回数を出力せよ．
入力例 1
4 2 2 1 1 2
出力例 1
2
まず，s=2+1=3 です． 以下のように操作することで，スコアを 4 以上にすることができます．
- (2,1,1,2) \to (A_3 と A_4 の値を入れ替える )\to (2,1,2,1) \to (A_2 と A_3 の値を入れ替える )\to (2,2,1,1)
1 回の操作では目標を達成できないため，必要な最小の操作回数は 2 になります．
入力例 2
3 1 3 2 1
出力例 2
-1
入力例 3
20 13 90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054
出力例 3
13
Score : 400 points
Problem Statement
We have an integer sequence of length N: A=(A_1,A_2,\cdots,A_N). Below in this problem, let the score of A be the sum of the first K terms of A. Additionally, let s be the score of the sequence A given in input.
You can do the following operation any number of times.
- Choose two adjacent elements of A and swap them.
Your objective is to make the score at least s+1. Determine whether the objective is achievable. If it is, find the minimum number of operations needed to achieve it.
Constraints
- 2 \leq N \leq 4 \times 10^5
- 1 \leq K \leq N-1
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
If the objective is not achievable, print -1.
If it is achievable, print the minimum number of operations needed to achieve it.
Sample Input 1
4 2 2 1 1 2
Sample Output 1
2
We have s=2+1=3. The following sequence of operations makes the score at least 4.
- (2,1,1,2) \to (swap A_3 and A_4)\to (2,1,2,1) \to (swap A_2 and A_3)\to (2,2,1,1)
The objective is not achievable in one operation, so the minimum number of operations needed is 2.
Sample Input 2
3 1 3 2 1
Sample Output 2
-1
Sample Input 3
20 13 90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054
Sample Output 3
13