Official Analysis (C++/Java)

Explanation

We can treat each interval between Nhoj's cows as a single problem. After computing the answer for each interval, we can select the $N$ most optimal cow placements for our answer.

There are two types of intervals we need to consider:

Leftmost/Rightmost Intervals

We can use a single cow to cut off Nhoj's cows on either edge. These cows earn all the tastiness left of the leftmost Nhoj cow and right of the rightmost Nhoj cow.

Middle Intervals

We have a one-cow and a two-cow answer for each middle interval.

For the one-cow answer, we find that regardless of where the cow is placed, it covers the same range that it beats Nhoj's cows. We can thus use a sliding window to compute the maximum gain from a single cow.

For the two-cow answer, we can place cows right before both of Nhoj's cows, thus gaining all the tastiness in the interval. We then calculate the gain from adding the second cow to be the two-cow tastiness minus the one-cow tastiness.

The one-cow answer shows the most optimal selection of tastiness in the interval. The two-cow answer is effectively the leftovers. Thus, the gain from the one-cow is always at least as good as the gain from the two-cow answer. Therefore, we can sort all the potential tastiness gains and select the $N$ largest ones to find our answer.

Implementation

Time Complexity: $\mathcal{O}((K+M)\log(K+M))$

Copy
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int k, m, n;
	cin >> k >> m >> n;

Copy
import java.io.*;
import java.util.*;

public class ClosestCowWins {
	static class Entry {
		int pos;
		long tastiness;

		Entry(int pos, long tastiness) {
			this.pos = pos;

Copy
k, m, n = map(int, input().split())

# store both patches and Nhoj's cows in one array
entries = []

for _ in range(k):
	pos, tasty = map(int, input().split())
	entries.append((pos, tasty))

for _ in range(m):