4575 . A5. 水獺與他的人工瀑布 (Waterfall)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

在題序開始之前，先來看otter的24hr直播(雖然這是海獺我找不到水獺的

已知水獺在他的棲息地放了 $N$ 個底面積皆為 $1m ^ 2$ 的水箱，每個水箱的高度分別為$a_i$，他把它們緊貼地排在一個直線上，這樣在把水注滿之後就可以在水箱中由上往下體驗人工瀑布了，而每個在第 $i$ 個水箱多出來的水皆只會流到第$i+1$個水箱，若其也是滿的，則會繼續流下去，因為水獺會帶建電在社團評鑑拿到前十名賺錢，所以就算 $a_i<a_{i+1}$ ，也會有人幫他放到下個水箱，這部分先暫且不用擔心

水獺每秒可以對每個水箱注入 $1m ^ 3$ 的水，然而對每個水箱同時注入水太浪費了，現在水獺想要在 $T$ 秒內把所有水箱注滿水，請問他至少要對幾個水箱注水

Input Format

第一行有二個正整數 $N$   $T$ 代表水獺有幾個水箱及水獺最久可以等多久
第二行有 $N$ 個整數，以空格分開，代表每個水箱依序的高度

$0<N<2\times10 ^ 5$
$0<a_i,\ T\le10 ^ 9$

Output Format

若水獺無法在時間內注滿所有水箱，請輸出-1
否則請輸出一正整數代表水獺至少需要對幾個水箱注水

Sample Input 1

5 10
9 7 6 4 1

Sample Output 1

3

Sample Input 2

5 5
4 8 7 6 3

Sample Output 2

-1

Sample Input 3

5 7
4 8 7 6 3

Sample Output 3

4

Hints

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

50.0% (1/2)

Tags

學術上機考 112 學年度

Problem Setter

Created by cjtsai

Subtasks

No. Testdata Range Constraints Score
1 0~15 $0\le N\le 1000$ 30
2 16~31 無其他限制 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1
6 1000 262144 65536 1
7 1000 262144 65536 1
8 1000 262144 65536 1
9 1000 262144 65536 1
10 1000 262144 65536 1
11 1000 262144 65536 1
12 1000 262144 65536 1
13 1000 262144 65536 1
14 1000 262144 65536 1
15 1000 262144 65536 1
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
Submit
Back to Top