謎解き公演がハシゴできるかを確かめるスクリプト

問題

問題文

F君はある日, $${N}$$種類の公演に参加しようとしている.
$${i}$$番目の公演のタイトルは$${S_i}$$, 所要時間は$${D_i}$$分であり, その日に$${K_i}$$回行われ, $${j}$$回目の公演の開始時刻は$${H_{i,j}}$$時$${M_{i,j}}$$分である.
F君が複数の公演に参加するとき, 間を$${B}$$分以上空けなくてはならない.
F君が全種類の公演に参加する方法を, 拘束時間が短い順に, いい感じに出力せよ.

制約

• $${N\leq8}$$

• $${K_i\leq8}$$

入力

$$
\begin{array}{l}
N\;B\\
S_1\;D_1\;K_1\\
H_{1,1}\;M_{1,1}\\
\vdots\\
H_{1,K_1}\;M_{1,K_1}\\
\vdots\\
S_N\;D_N\;K_N\;\\
H_{N,1}\;M_{N,1}\\
\vdots\\
H_{N,K_N}\;M_{N,K_N}
\end{array}
$$

入力例

4 15
kaizo 120 3
12 45
15 45
18 30
bokyaku 110 4
10 00
12 30
15 30
18 00
oke 80 6
9 50
11 40
13 50
15 40
17 30
19 20
toke 80 4
9 40
13 40
17 20
19 10

コード

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

int N, B, D[8], K[8], T[8][8], H[8][8], M[8][8];
string S[8];

int a[8];
bool next() {
	for (int i = N - 1; i >= 0; --i) {
		++a[i];
		if (a[i] < K[i])
			return 1;
		a[i] = 0;
	}
	return 0;
}

struct ev {
	int i, s, f;
	ev() {
	}
	ev(int i, int d, int h, int m) :
			i(i), s(h * 60 + m), f(h * 60 + m + d) {
	}
	bool operator<(const ev &r) const {
		return s < r.s;
	}
};
string time2str(int T) {
	char s[6];
	snprintf(s, 6, "%2d:%02d", T / 60, T % 60);
	return s;
}
ostream& operator<<(ostream &os, const vector<ev> &v) {
	size_t m = 0;
	for (auto s : S)
		m = max(m, s.size());
	for (int i = 0; i < N; ++i)
		os << setw(m + 1) << left << S[v[i].i] << time2str(v[i].s) << ' '
				<< time2str(v[i].f) << '\n';
	os << "[total " << v[N - 1].f - v[0].s << " min]\n";
	return os;
}

vector<vector<ev>> ans;

int main() {
	cin >> N >> B;
	for (int i = 0; i < N; ++i) {
		cin >> S[i] >> D[i] >> K[i];
		for (int j = 0; j < K[i]; ++j)
			cin >> H[i][j] >> M[i][j];
	}
	do {
		vector<ev> v;
		for (int i = 0; i < N; ++i)
			v.emplace_back(i, D[i], H[i][a[i]], M[i][a[i]]);
		sort(v.begin(), v.end());
		bool flag = 1;
		for (int i = 0; i < N - 1; ++i)
			if (v[i].f + B > v[i + 1].s)
				flag = 0;
		if (flag)
			ans.push_back(v);
	} while (next());
	sort(ans.begin(), ans.end(), [](auto &x, auto &y) {
		return x[N - 1].f - x[0].s < y[N - 1].f - y[0].s;
	});
	for (auto v : ans)
		cout << v << '\n';
}