Need help in optimization!
Appy loves balloons! She wants you to give her balloons on each of N consecutive days (numbered 1 through N); let's denote the number of balloons Appy wants on day i by Ai. The problem is that you only have M balloons. Fortunately, you can give her candies instead of balloons as well. On each day i, Appy accepts Bi candies per each balloon you do not give her — formally, if you give Appy Xi balloons on day i, then you have to give her Ci=max(0,Ai−Xi)⋅Bi candies as well.
Your task is to minimize the maximum number of candies you give Appy on some day — find the minimum possible value of max(C1,C2,C3,...,CN).
Input:
The first line of the input contains two space-separated integers N and M.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains N space-separated integers B1,B2,…,BN.
Constraints:
1≤N≤10^5
0≤M≤10^18
0≤Ai≤10^9 for each valid i
0≤Bi≤10^9 for each valid i
Example Input:
5 3
1 2 3 4 5
1 2 3 4 5
Output:
15
Explanation:
If you give Appy 0,0,0,1,2 balloons on days 1 through 5, then the required numbers of candies on each day are 1,4,9,12,15. The maximum number of candies is 15, required on day 5.
I have solved this question for 27 points but getting TLE for 3 test cases.
I solved this using greedy method in which I was giving balloons only for the days with maximum No of candies to give.I ran a while loop till the total no of balloons are equal to zero.
Can anyone suggest a hint on how to solve this problem?
Thank You!
Your task is to minimize the maximum number of candies you give Appy on some day — find the minimum possible value of max(C1,C2,C3,...,CN).
Input:
The first line of the input contains two space-separated integers N and M.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains N space-separated integers B1,B2,…,BN.
Constraints:
1≤N≤10^5
0≤M≤10^18
0≤Ai≤10^9 for each valid i
0≤Bi≤10^9 for each valid i
Example Input:
5 3
1 2 3 4 5
1 2 3 4 5
Output:
15
Explanation:
If you give Appy 0,0,0,1,2 balloons on days 1 through 5, then the required numbers of candies on each day are 1,4,9,12,15. The maximum number of candies is 15, required on day 5.
I have solved this question for 27 points but getting TLE for 3 test cases.
I solved this using greedy method in which I was giving balloons only for the days with maximum No of candies to give.I ran a while loop till the total no of balloons are equal to zero.
Can anyone suggest a hint on how to solve this problem?
Thank You!
I've already gone through that thread.I couldn't find any relevant info in that thread.
Can you stop making new accounts?
This is not a homework website and we have moderators on this website who work for codechef to specifically ban you. If you are incapable of putting the slightest shred of effort into your posts, you should stop trying.
Also note that the posts were identical before it was modified with code tags.
This is not a homework website and we have moderators on this website who work for codechef to specifically ban you. If you are incapable of putting the slightest shred of effort into your posts, you should stop trying.
Also note that the posts were identical before it was modified with code tags.
Last edited on
| ..we have moderators on this website who work for codechef |
@poteto,
are you sure? I have been around for some time and never heard about moderators. Who are they ?
| sudowudo wrote: |
|---|
| I've already gone through that thread.I couldn't find any relevant info in that thread. |
If no-one gave relevant info the last time this question was asked, what makes you think asking the same question again will magically cause something different to happen?
Just because you were unsatisfied with the answers this question got last time, does not justify starting new threads for the same question.
| Thomas1965 wrote: |
|---|
| are you sure? I have been around for some time and never heard about moderators. Who are they ? |
Many users here have limited moderation powers. For example, if I were to report one of sudowudo's posts for, say, posting duplicate threads, or trying to cheat on a programming competition, that post would be deleted.
Whether there is anyone here who (a) has such abilities and (b) works for Codechef, I don't know.
However, we do know that the moderators at Codechef are aware that people are using this forum to cheat on the competitions, and have disqualified people based on what they see posted here.
Last edited on
Besides, it is not important whether any of us is one of them. What does count is that the participants of contests believe so and therefore "play it safe and honest".
Well, the participants now know that the Codechef adjudicators are monitoring these forums, and that if they try and use these forums to cheat, they are likely to be found out and disqualified.
Topic archived. No new replies allowed.