help with a problem
source link: https://codeforces.com/blog/entry/108475?f0a28=1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
help with a problem
you have n instant cup noodles pack. The ith pack takes ci minutes to cook after hot water is added to it, and it satisfies your hunger by an amount of hi. Now, you are running late for your college and you have only m minutes left to cook the noodles. You wish to satisfy your hunger to a maximum level. But in one minute, you can add hot water to one cup only. You have to find the maximum level of hunger that you can satisfy in m minutes. Consider that adding hot water and eating the noodles doesn't require any time.
- constraints;
- 1<=t<=10
- 1<=n<=10000
- 1<=m<=100000
- 1<=ci<=100000
- 1<=hi<=10000
sample:
- output — 12
I thought of applying dp but the constraints are too large. Can anyone suggest a better greedy approach.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK