A - Larger Score

Contest Duration: 2022-04-09(Sat) 12:00 - 2022-04-09(Sat) 14:00 (local time) (120 minutes) Back to Home

A - Larger Score Editorial

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 を出力せよ．可能である場合，必要な最小の操作回数を出力せよ．

入力例 1Copy

Copy

4 2
2 1 1 2

出力例 1Copy

Copy

まず， $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$ になります．

入力例 2Copy

Copy

3 1
3 2 1

出力例 2Copy

Copy

-1

入力例 3Copy

Copy

20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

出力例 3Copy

Copy

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 1Copy

Copy

4 2
2 1 1 2

Sample Output 1Copy

Copy

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 2Copy

Copy

3 1
3 2 1

Sample Output 2Copy

Copy

-1

Sample Input 3Copy

Copy

20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

Sample Output 3Copy

Copy