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:
- If FJ places a cow immediately to the left of FNs left-most cow, then FJ owns all grassy patches to its left.
- Similarly, if FJ places a cow immediately to the right of FNs right-most cow, the FJ owns all grassy patches to its right.
- In an interval which is enclosed by two of FNs cows, if FJ paces one cow, then FJ owns any grassy patches that fall within half of the interval that surrounds the cow.
- In an interval which is enclosed by two of FNs cows, if FJ places one cow at each of the ends of the intervals, then FJ owns all grassy patches in this intervals.
Adding more than 2 cows in a interval enclosed by FNs cows and adding more than 1 cow in a interval enclosed by one of FNs cows is unnecessary.
If FJ adds one cow in a interval enclosed by FNs cows, FJ can only own grassy patches in half of the interval. So, to calculate the maximum score that can be obtained in this range using one cow, we can maintain a sliding window of length L/2, using the two pointer method. The score for a sliding window is the sum of all yumminess values of grassy patches that fall in this window. Basically, find the maximum sliding window sum for every interval like this.
If FJ wants to own all the grassy patches in this interval , then he would have to place two cows. The score for placing two cows would be the sum of all yumminess values of all grassy patches in this interval . But, this would also include the maximum sliding window sum. To exclude this, subtract the maximum sliding window from the total sum of grassy patches.
FJ can also place cows as described in points 1 and 2, to own all grassy patches enclosed by one of FNs cows. The score for these patches is the sum of all yumminess values of all patches here.
FJ can only choose the best N scores, since he only has N cows. Sort all the scores calculated before and sum up the N highest. The answer is this sum.
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int k, m, n;
cin >> k >> m >> n;
vector <pair <long long, long long>> grass(k);
for (int i = 0; i < k; i++)
cin >> grass[i].first >> grass[i].second;
vector <long long> nhoj(m);
for (int i = 0; i < m; i++)
cin >> nhoj[i];
sort(begin(nhoj), end(nhoj));
sort(begin(grass), end(grass));
vector <long long> sums;
long long p1 = 0, p2 = 0;
long long tot_sum = 0, max_half_sum = 0, curr_sum = 0;
// add the interval that comes before the first nhoj cow
while (grass[p2].first < nhoj[0]) {
curr_sum += grass[p2].second;
p2++;
}
sums.push_back(curr_sum);
curr_sum = 0;
p1 = p2;
for (int i = 0; i < m; i++) {
long long start = nhoj[i], end = nhoj[i+1];
long long L = end - start;
long long window_len = L / 2;
curr_sum = max_half_sum = tot_sum = 0;
while (grass[p2].first < end && p2 < k && p1 < k) {
// basic idea: sliding window should be of size window_len
// sliding window size is the distance covered by FJ's
// cows, including the spaces between them
tot_sum += grass[p2].second;
curr_sum += grass[p2].second;
p2++;
if (grass[p2].first - grass[p1].first + 1 > window_len){
max_half_sum = max(max_half_sum, curr_sum);
curr_sum -= grass[p1].second;
p1++;
}
}
sums.push_back(max_half_sum);
sums.push_back(tot_sum - max_half_sum);
p1 = p2;
}
// add the interval the comes after the last nhoj cow
curr_sum = 0;
while (p2 < k) {
curr_sum += grass[p2].second;
p2++;
}
sums.push_back(curr_sum);
sort(begin(sums), end(sums));
long long ans = 0;
for (int i = sums.size()-1; i >= 0 && n > 0; i--, n--)
ans += sums[i];
cout << ans << '\n';
return 0;
}
Comments