c269: 裴裴與女生們
Tags :
Accepted rate : 49人/61人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-09-23 10:31

Content

裴裴剛上大學,決定來認識一些女生。校園裡有n個女生,分別編號為1~n,她們都有一個共同的特性,就是如果你花si的時間陪伴她,她就會滿足,你就會從她身上得到vi的好感度,但花超過si的時間陪她也不會得到額外的好感度

但是經過裴裴的精心研究發現,這些女生可以細分為兩種類型。第一種類型的女生有一個特性,就是她們回饋你的好感度正比於你陪他們的時間。也就是如果第i個女生是第一類的女生,你花si/k的時間陪她,就會得到vi/k的好感度。第二種類型的女生就比較麻煩了,除非你讓他滿足(也就是花si的時間陪她),不然你是不會得到任何好感度的。裴裴很忙,他只有T單位的時間可以拿來陪女生,請算出裴裴最多可以得到多少好感度?為了方便輸出,請自動將答案四捨五入至整數位。

例如:

有4個女生資料分別為下,且裴裴有10單位的時間

編號1:s1=5,v1=15,第二類

編號2:s2=5,v2=14,第二類

編號3:s3=4,v1=13,第二類

編號4:s4=8,v2=17,第二類

裴裴的最佳策略是花5單位的時間陪伴編號1的女生以及5單位的時間陪伴編號2的女生,如此可得到最多的好感度15+14=29.

若編號4的女生改為第一類,則最佳策略是花5單位的時間陪伴編號1的女生,4單位的時間陪伴編號3的女生,以及1單位的時間陪伴編號4的女生,如此可得到最多的好感度15+13+17/8=30.125.(四捨五入後為30)

Input

測資的第一行有兩個整數n,T分別代表有幾個女生以及裴裴有多少單位的時間。接下來n行中每行有3個數字si,vi,pi描述這個女生。如果裴裴花si的時間陪伴她,她就會滿足,裴裴就會從她身上得到vi的好感度,且這個女生是屬於第pi類的女生。

(1≦n≦10000,1≦T,si≦1000,1≦vi≦109,pi=1或2)

Output

對於每一筆測資,請輸出一個數字代表裴裴能獲得的最大好感度。輸出的數字請四捨五入到整數。

Sample Input #1
//sample input 1
4 10
5 15 2
5 14 2
4 13 2
8 17 2
//sample input 2
4 10
5 15 2
5 14 2
4 13 2
8 17 1
Sample Output #1
//sample output 1
29
//sample output 2
30
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (30%): 1.0s , <1M
公開 測資點#1 (30%): 1.0s , <1M
公開 測資點#2 (40%): 1.0s , <1M
Hint :

測資配置:

(1)測資一(30分)  所有女生都是第一類的

(2)測資二(30分)  所有女生都是第二類的

(3)測資三(40分)  無特殊限制

Tags:
出處:
[管理者:
VacationClub (雄中公假社)
]


ID User Problem Subject Hit Post Date
18006
joshlin1999 (๑˙―˙๑)
c269
464 2019-06-09 01:35