Official Analysis

Explanation

Since $M = 10$ is given, we can iterate through all $2^{10}$ possible subsets of air conditioners. For each of them, we check if this subset of air conditioners satisfy the requirements of the cows by iterating through all possible positions $i \in [1;100]$. For each position $i$, we can iterate through all available air conditioners in the current subset to find out the temperature reduced at $i$ and iterate through all cows to find the cow at this position and its demand. If the requirement at each position is fulfilled, we update the minimal cost accordingly.

We can generate subsets with recursion or bitmasks: both ways are presented below.

Solution 1: Subset with Recursion

Time Complexity: $\mathcal{O}(2^M \cdot 100 \cdot (M + N))$

Copy
cows = []  # List to store {s, t, c} for each cow
air_conditioners = []  # List to store {a, b, p, m} for each air conditioner

# the minimum amount of money needed to keep all cows comfortable
min_cost = float("inf")


def update():
	"""
	Based on 'uses', determine if the current subset of air conditioners suffices

Solution 2: Subset with Bitmask

Time Complexity: $\mathcal{O}(2^M \cdot 100 \cdot (M + N))$

Copy
from typing import NamedTuple

MAX_STALL = 100


class Cow(NamedTuple):
	start: int
	end: int
	cool_req: int