TopCoder

Caido
Waimai

User's AC Ratio

68.4% (13/19)

Submission's AC Ratio

10.6% (45/423)

Tags

Description

盩僰麌,一名來自大陸的競程選手,平時除了打開電腦在各大Judge上刷一排排綠色的AC以外,並沒有其他特別的嗜好。

盩僰麌居住的地方有著和常人不一樣的時間度量方法,也就是說,他們口中的一個禮拜其實是正常人所認為的K天。
「又是一個無趣的禮拜」盩僰麌一邊看著題目一邊心想,的確,解題對他來說已經太容易,甚至有點索然無味了。雖然一直切題不是什麼吸引人的事,為了不讓自己看起來很頹,還是希望可以每天都寫一些題目。於是他打開電腦,選了N道題目,並把每道題目的難易程度量化,第i道題的難度是di

盩僰麌刷題的原則相當簡單,每天可以選任意的題目量來做,可是每天都至少要寫一題,此外,為了避免自己搞錯題目的編號,他決定順著前一天的題號做下去,並且每次都做編號連續的一串題目(也就是說,第一天從編號1的開始寫,而對於第i天,若第i天做的第一題及最後一題的題號分別是si,ti,則si=ti1+1(i>1))。盩僰麌想要在刷題中還是盡可能尋找一些樂趣,對於每一天,他會從他做的第i題(假設編號為x)中得到(Ci)×dx的樂趣(由於一直刷題也會感到無趣厭惡,因此Ci可能為負的),而一整天的樂趣就是這天刷的每一題帶給他的樂趣總和。

在刷題的同時,盩僰麌還想要同時跟大家裝弱,宣稱自己其實一整天都在耍廢。群眾的目光是銳利的,他們會翻閱盩僰麌的Submission並找出AC最多題目的一天(假設那天刷了Y題)用以衡量盩僰麌的裝弱虛實,此時若盩僰麌宣稱自己一個禮拜每天刷的題數都小於Y的話,他的裝弱便會被識破。

兼顧刷題樂趣跟裝弱帶來的喜悅是非常重要的,請你告訴盩僰麌,在他一個禮拜刷題總樂趣至少R的情況下,他最多能裝得多弱(也就是他最少能說自己每天寫的題數都不超過多少)。

Input Format

第一行包含三個正整數N,K,R,C,代表總題數、大陸一星期有幾天、盩僰麌至少要獲得多少樂趣以及決定樂趣的係數。
第二行包含N個非負整數di,代表第i題的難度。

對於所有的測資,KN105,K20,R1015,di105,C105,NK5×105

子任務(測資)額外限制分數
1(0~1)K=11
2(2~7)K=27
3(8~15)N80015
4(8~28)N300026
4(0~35)NK2×10524
5(0~50)無限制27

Output Format

輸出一個整數代表盩僰麌最少能宣稱自己只寫幾題,若盩僰麌就算不裝弱也不能達到自己想要的樂趣,輸出-1

Sample Input 1

10 2 56 4
10 1 2 3 1 1 2 10 1 1

Sample Output 1

6

Sample Input 2

3 1 5 3
1 2 3

Sample Output 2

-1

Hints

範例測資一中,盩僰麌在第一天刷編號16的題目,獲得樂趣(41)×10+(42)×1+(43)×2+(44)×3+(45)×1+(46)×1=31,第二天刷編號710的題目,獲得樂趣(41)×2+(42)×10+(43)×1+(44)×1=27,總樂趣31+27=58,是最佳的方案。

範例測資二中,唯一一種可行的方法為在第一天刷編號13的題目獲得總樂趣4,不能達到自己設的目標。

Problem Source

Problem Set by wayntuinfor
2022.02.01 Update: Input Format 修正「第二行包含N個正整數di」→「第二行包含N個非負整數di

Subtasks

No. Testdata Range Score
1 0~1 1
2 2~7 7
3 8~15 15
4 8~28 26
5 0~35 24
6 0~50 27

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 5 6
1 1000 65536 262144 1 5 6
2 1000 65536 262144 2 5 6
3 1000 65536 262144 2 5 6
4 1000 65536 262144 2 5 6
5 1000 65536 262144 2 5 6
6 1000 65536 262144 2 5 6
7 1000 65536 262144 2 5 6
8 1000 65536 262144 3 4 5 6
9 1000 65536 262144 3 4 5 6
10 1000 65536 262144 3 4 5 6
11 1000 65536 262144 3 4 5 6
12 1000 65536 262144 3 4 5 6
13 1000 65536 262144 3 4 5 6
14 1000 65536 262144 3 4 5 6
15 1000 65536 262144 3 4 5 6
16 2000 65536 262144 4 5 6
17 2000 65536 262144 4 5 6
18 2000 65536 262144 4 5 6
19 2000 65536 262144 4 5 6
20 2000 65536 262144 4 5 6
21 2000 65536 262144 4 5 6
22 2000 65536 262144 4 5 6
23 2000 65536 262144 4 5 6
24 2000 65536 262144 4 5 6
25 2000 65536 262144 4 5 6
26 2000 65536 262144 4 5 6
27 2000 65536 262144 4 5 6
28 2000 65536 262144 4 5 6
29 1000 65536 262144 5 6
30 1000 65536 262144 5 6
31 1000 65536 262144 5 6
32 1000 65536 262144 5 6
33 1000 65536 262144 5 6
34 1000 65536 262144 5 6
35 1000 65536 262144 5 6
36 1000 65536 262144 6
37 1000 65536 262144 6
38 1000 65536 262144 6
39 1000 65536 262144 6
40 1000 65536 262144 6
41 1000 65536 262144 6
42 1000 65536 262144 6
43 1000 65536 262144 6
44 1000 65536 262144 6
45 1000 65536 262144 6
46 1000 65536 262144 6
47 1000 65536 262144 6
48 1000 65536 262144 6
49 1000 65536 262144 6
50 1000 65536 262144 6