**Subtask 1:**

*Solution 1:* We can greedily build towers one at a time as such: process
the remaining cows from heaviest to lightest, adding a cow to the current tower
if possible. Repeat this $M$ times, once for each tower.

Code:

N, M, K = map(int, input().split()) cows = [] for _ in range(N): w, a = map(int, input().split()) cows += [w] * a cows.sort(reverse=True) answer = 0 for _ in range(M): remaining_cows = [] current_cow = 1e100 #arbitrary large number for cow in cows: if cow + K <= current_cow: current_cow = cow answer += 1 else: remaining_cows += [cow] if len(remaining_cows) == 0: break cows = remaining_cows print(answer)

Time Complexity: $O(c^2)$, where $c$ is the number of cows.

*Solution 2a:* Process the cows from heaviest to lightest. When we process
a cow, we try to put it on any tower. This is always optimal since we could put
any of the remaining cows on a tower that the current cow can be placed on, so
it doesn't matter where we place the current cow.

Code:

N, M, K = map(int, input().split()) cows = [] for _ in range(N): w, a = map(int, input().split()) cows += [w] * a cows.sort(reverse=True) answer = 0 towers = [1e100]*min(M, len(cows)) for cow in cows: for i in range(M): if cow + K <= towers[i]: towers[i] = cow answer += 1 break print(answer)

** Solution 2b:** Instead of placing the cow on an arbitrary tower, we only
try to place it on the tower with the heaviest cow on top. This is because if it
is possible to place a cow on a tower, it is possible to place it on the tower
with the heaviest cow on top.

Time Complexity: $O(c^2)$

Note that the number of towers is bounded by the number of cows, since if the number of towers is greater than the number of cows, we can just remove the excess towers.

**Subtask 2:**

We can optimize * solution 2b * in ** subtask 1 ** by speeding up the
search for the heaviest cow. We can do this by keeping a sorted queue of towers
where the front of the queue is the tower with the heaviest cow on top. When we
place the current cow on a tower, we move that tower to the back of the queue
since the current cow is lighter than all of the cows processed before it.

Time complexity: $O(c\log c)$, where the log factor comes from sorting the cows by weight.

Code:

from collections import deque N, M, K = map(int, input().split()) cows = [] for _ in range(N): w, a = map(int, input().split()) cows += [w] * a cows.sort(reverse=True) answer = 0 towers = deque([1e100]*min(M, len(cows))) for cow in cows: if cow + K <= towers[0]: answer += 1 towers.popleft() towers.append(cow) print(answer)

**Subtask 3:** Instead of processing individual cows and towers, compress
them into (weight, count) pairs. See the code for the details. The time
complexity of the remaining portion of the code after the sorting step is
bounded by the number of insertions to and deletions from the queue. Both of
these are at most $N$, so the time complexity of the remaining portion is
$O(N)$.

Overall time complexity: $O(N \log N)$

Code:

from collections import deque N, M, K = map(int, input().split()) pairs = [] for _ in range(N): w, a = map(int, input().split()) pairs.append([w, a]) pairs.sort(reverse = True) towers = deque() towers.append([1e100, M]) answer = 0 for w, a in pairs: remaining = a while len(towers) > 0 and remaining > 0 and w + K <= towers[0][0]: if towers[0][1] > remaining: towers[0][1] -= remaining remaining = 0 else: remaining -= towers[0][1] towers.popleft() cnt = a - remaining if cnt > 0: towers.append([w, cnt]) answer += cnt print(answer)

Using an ordered set rather than a deque can also pass with given constraints.

Danny Mittal's code:

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class BovineAcrobaticsBR { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tokenizer = new StringTokenizer(in.readLine()); int n = Integer.parseInt(tokenizer.nextToken()); int m = Integer.parseInt(tokenizer.nextToken()); int k = Integer.parseInt(tokenizer.nextToken()); CowGroup[] cowGroups = new CowGroup[n]; for (int j = 0; j < n; j++) { tokenizer = new StringTokenizer(in.readLine()); int weight = Integer.parseInt(tokenizer.nextToken()); int amt = Integer.parseInt(tokenizer.nextToken()); cowGroups[j] = new CowGroup(weight, amt); } Arrays.sort(cowGroups, Comparator.comparingInt(group -> group.weight)); TreeSet<CowGroup> treeSet = new TreeSet<>(Comparator.comparingInt(group -> group.weight)); int towers = 0; long answer = 0; for (CowGroup group : cowGroups) { int disp = group.amt; while (disp > 0) { CowGroup floor = treeSet.floor(new CowGroup(group.weight - k, 0)); if (floor == null) { break; } treeSet.remove(floor); if (floor.amt <= disp) { disp -= floor.amt; } else { treeSet.add(new CowGroup(floor.weight, floor.amt - disp)); disp = 0; } } towers -= group.amt - disp; int canAdd = Math.min(group.amt, m - towers); towers += canAdd; answer += canAdd; treeSet.add(new CowGroup(group.weight, canAdd)); } System.out.println(answer); } static class CowGroup { final int weight; final int amt; CowGroup(int weight, int amt) { this.weight = weight; this.amt = amt; } } }