Official Analysis (Python)

Explanation

Notice that it is optimal to place the heaviest cows at the bottom and the lightest cows at the top, which makes the gap as large as possible. Therefore, we can sort the cows from heaviest to lightest. We maintain a sorted queue with these cows. For each cow, if it can't be added to the tower at the front of our queue, we know that it cannot be added to any tower, and thus that cow can be ignored.

However, this takes $\mathcal{O}(N \log N)$ operations for $N$ total cows, which is too slow. To optimize this, instead of considering cows individually, we can group towers which have equivalent cow weights at the top together. Then, by maintaining a queue of groups of towers sorted by weight, we can process all cows in $\mathcal{O}(N)$.

Each time we process a group of cows with the same weight, we will end up adding a new group of cows to our queue. Because we are processing our cows in sorted order, this newest group of towers will be placed at the back of the queue, which maintains the queue's sorted order.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<array<int, 2>> cowGroups(n);
	for (int i = 0; i < n; i++) {
		cin >> cowGroups[i][0] >> cowGroups[i][1];

Copy
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)
# Sort by descending weight

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

public class Main {
	static class Group {
		final long weight;
		final long amount;

		Group(long weight, long amt) {
			this.weight = weight;