COWCAR - Cow Cars
N (1 ≤ N ≤ 50,000) cows conveniently numbered 1, ..., N are driving in separate cars along a highway in Cowtopia. Cow i can drive in any of M different high lanes (1 ≤ M ≤ N) and can travel at a maximum speed of Si (1 ≤ Si ≤ 1,000,000) km/hour.
After their other bad driving experience, the cows hate collisions and take extraordinary measures to avoid them. On this highway, cow i reduces its speed by D (0 ≤ D ≤ 5,000) km/hour for each cow in front of it on the highway (though never below 0 km/hour). Thus, if there are K cows in front of cow i, the cow will travel at a speed of max(Si - D*K, 0). While a cow might actually travel faster than a cow directly in front of it, the cows are spaced far enough apart so crashes will not occur once cows slow down as described.
Cowtopia has a minimum speed law which requires everyone on the highway to travel at a a minimum speed of L (1 ≤ L ≤ 1,000,000) km/hour, so sometimes some of the cows will be unable to take the highway if they follow the rules above. Write a program that will find the maximum number of cows that can drive on the highway while obeying the minimum speed limit law.
The first line contains the four integers N, M, D, and L. For the next N lines, line i+1 contains the integer Si.
Print a single integer denoting the maximum number of cows that can take the highway.
Input: 3 1 1 5 5 7 5 Output: 2
We can obtain two cows by putting either cow with speed 5 first and the cow with speed 7 second.
Wow, I was almost sure it will get TLE but AC on first time! :D
int also works. Depends on your approach.
Ghost Of Perdition:
why long long
mala da.... annamala:
Use long long....Costed me 2 wa's...
the description is just fine, though it could have been better...anyway the problem is simple enough...
ques... language is improper!!!!!