/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は、アルバイト先の店長として、今月のシフト M コマを N 人のスタッフに割り当てようとしています。
各スタッフ i（ 1 \leq i \leq N ）には、今月働ける上限コマ数 R_i が決まっています。高橋君は、各スタッフへの割り当てコマ数 X_i を、0 \leq X_i \leq R_i を満たす非負整数として決めます。
割り当ては、次の合計条件を満たさなければなりません。
- 合計条件： 割り当てるシフトの合計はちょうど M コマである。すなわち、X_1 + X_2 + \cdots + X_N = M 。
合計条件を満たす割り当てが 1 つ以上存在するとき、高橋君は不公平度をできるだけ小さくしたいと考えています。ここで、各スタッフ i について、上限コマ数と実際の割り当てコマ数の差 R_i - X_i を「スタッフ i の未割り当て枠」と呼びます。全スタッフの未割り当て枠の最大値、すなわち
\max_{1 \leq i \leq N} (R_i - X_i)
を「不公平度」と定義します。
不公平度が大きいということは、上限に対して割り当てが極端に少ないスタッフが存在することを意味します。高橋君は、そのようなスタッフの不満をできるだけ抑えるため、不公平度を最小化したいのです。
合計条件を満たす割り当てが存在するとき、不公平度の最小値を求めてください。合計条件を満たす割り当てが存在しない場合は -1 を出力してください。
なお、合計条件を満たす割り当てが存在しないのは、M > R_1 + R_2 + \cdots + R_N である場合、またその場合に限ります。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 10^{18}
- 0 \leq R_i \leq 10^{18}（ 1 \leq i \leq N）
- 入力はすべて整数である。
注意： R_1 + R_2 + \cdots + R_N は 64 ビット符号付き整数の範囲を超える場合があります。
入力
N M R_1 R_2 \cdots R_N
- 1 行目には、スタッフの人数を表す整数 N と、割り当てるシフトの総コマ数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各スタッフの上限コマ数を表す整数 R_1, R_2, \ldots, R_N が、スペース区切りで与えられる。
出力
不公平度の最小値を 1 行で出力してください。合計条件を満たす割り当てが存在しない場合は -1 を出力してください。
入力例 1
3 7 4 3 5
出力例 1
2
入力例 2
3 20 5 5 5
出力例 2
-1
入力例 3
5 1000000000000000000 300000000000000000 200000000000000000 400000000000000000 100000000000000000 500000000000000000
出力例 3
100000000000000000
Score : 366 pts
Problem Statement
Takahashi, as the manager of his part-time workplace, is trying to assign this month's M shift slots to N staff members.
Each staff member i (1 \leq i \leq N) has a predetermined maximum number of slots R_i they can work this month. Takahashi determines the number of slots X_i assigned to each staff member as a non-negative integer satisfying 0 \leq X_i \leq R_i.
The assignment must satisfy the following total condition:
- Total condition: The total number of assigned shifts is exactly M slots. That is, X_1 + X_2 + \cdots + X_N = M.
When at least one assignment satisfying the total condition exists, Takahashi wants to minimize the unfairness. Here, for each staff member i, the difference R_i - X_i between their maximum slots and their actually assigned slots is called the "unassigned capacity of staff member i". The maximum unassigned capacity across all staff members, namely
\max_{1 \leq i \leq N} (R_i - X_i)
is defined as the "unfairness".
A large unfairness means that there exists a staff member whose assignment is extremely small relative to their maximum. Takahashi wants to minimize the unfairness in order to reduce the dissatisfaction of such staff members as much as possible.
When an assignment satisfying the total condition exists, find the minimum value of the unfairness. If no assignment satisfying the total condition exists, output -1.
Note that an assignment satisfying the total condition does not exist if and only if M > R_1 + R_2 + \cdots + R_N.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 10^{18}
- 0 \leq R_i \leq 10^{18} (1 \leq i \leq N)
- All input values are integers.
Note: R_1 + R_2 + \cdots + R_N may exceed the range of a 64-bit signed integer.
Input
N M R_1 R_2 \cdots R_N
- The first line contains an integer N representing the number of staff members and an integer M representing the total number of shift slots to assign, separated by a space.
- The second line contains integers R_1, R_2, \ldots, R_N representing the maximum number of slots for each staff member, separated by spaces.
Output
Output the minimum value of the unfairness in one line. If no assignment satisfying the total condition exists, output -1.
Sample Input 1
3 7 4 3 5
Sample Output 1
2
Sample Input 2
3 20 5 5 5
Sample Output 2
-1
Sample Input 3
5 1000000000000000000 300000000000000000 200000000000000000 400000000000000000 100000000000000000 500000000000000000
Sample Output 3
100000000000000000