题解

#include <bits/stdc++.h>
using namespace std;

struct Cow {
	int height;
	int weight;
	int strength;
};

int main() {
	int n;
	int h;
	cin >> n >> h;

	vector<Cow> cows(n);
	for (int i = 0; i < n; i++) {
		cin >> cows[i].height >> cows[i].weight >> cows[i].strength;
	}
	vector<pair<int, int>> dp(1 << n);
	dp[0] = {0, INT32_MAX};

	for (int i = 1; i < (1 << n); i++) {
		dp[i] = {0, -1};

		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) {
				dp[i].first += cows[j].height;

				int prev = i ^ (1 << j);
				dp[i].second =
				    max(dp[i].second, min(dp[prev].second - cows[j].weight,
				                          cows[j].strength));
			}
		}
	}

	int max_safety = -1;
	for (int i = 1; i < (1 << n); i++) {
		if (dp[i].first >= h) { max_safety = max(dp[i].second, max_safety); }
	}
	if (max_safety < 0) {
		cout << "Mark is too tall" << endl;
	} else {
		cout << max_safety << endl;
	}
}