USACO 2021 December Contest, Silver Problem 1- Closest Cow Wins
Problem Link Algorithm Used: 2P, Sliding Window, Sorting Time Complexity: O(N + M) Thanks to Alphastar USACO Training for making this video, which helped me understand this problems solution. In this problem, there are K grassy patches, situated on a number line, whose positions are distinct integers in the range 0 to 10⁹. Each of the grassy patches has a yumminess value associated with it. Farmer Nhoj has situated his M cows on the number line (not necessarily on grassy patches), and FJ needs to position his N cows too. The grassy patches will be owned by the farmer whose cow(s) are closest to the patch. If FJs and Farmer Nhojs (will be called FN now) cows are equally close to a grassy patch, then FN owns that patch. If FJ owns a patch, then his score increases by the yumminess value of that patch. Position FJs cows such that his score is maximal (FJ may place his cows on fractional positions on the number line too). To solve this problem, here are a few observations...