#pragma region Macros #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME #define _rep1(i, n) for (long long i = 0; i < n; i++) #define _rep2(i, a, b) for (long long i = a; i < b; ++i) #define _rep3(i, a, b, t) \ for (long long i = a; i * (t / abs(t)) < b * (t / abs(t)); i += t) #define rep(...) OVERLOAD(__VA_ARGS__, _rep3, _rep2, _rep1, _)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define sz(x) (int)x.size() #define fi first #define se second #define pb push_back #define eb emplace_back #define mp make_pair #define pcnt __builtin_popcountll #define SORT(v) sort(all(v)) #define UNIQUE(v) \ SORT(v); \ v.erase(unique(v.begin(), v.end()), v.end()); #define COPY(A, B) copy(all(A), B.begin()); #define REV(v) reverse(all(v)) #define MAX(x) *max_element(all(x)) #define MIN(x) *min_element(all(x)) #ifdef LOCAL #define dbg(x) \ { \ cout << __LINE__ << " : " << #x << " = "; \ print(x); \ } #define IS_LOCAL true #else #define dbg(x) true #define IS_LOCAL false #endif using namespace std; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template bool chmin(T& k, T m) { bool ret = k > m; k = min(k, m); return ret; } template bool chmax(T& k, T m) { bool ret = k < m; k = max(k, m); return ret; } template inline void print(const vector& v, string s = " ") { for (int i = 0; i < (int)v.size(); i++) cout << v[i] << (i != (int)v.size() - 1 ? s : ""); cout << "\n"; } template inline void print(const pair& p) { cout << p.first << " " << p.second << endl; } template inline void print(const T& x) { cout << x << "\n"; } template inline void print(const vector>& v) { for (auto&& p : v) print(p); } void yes(bool a) { cout << (a ? "yes" : "no") << endl; } void YES(bool a) { cout << (a ? "YES" : "NO") << endl; } void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; } template T SUM(vc As) { T ret = 0; for (T a : As) ret += a; return ret; } #pragma endregion const ll INF = numeric_limits::max(); /** * @brief Dinic(最大流) * @docs docs/dinic.md */ template struct Dinic { const flow_t INF; struct edge { int to; flow_t cap; int rev; bool isrev; int idx; }; vector> graph; vector min_cost, iter; explicit Dinic(int V) : INF(numeric_limits::max()), graph(V) {} void add_edge(int from, int to, flow_t cap, int idx = -1) { assert(cap >= 0); graph[from].emplace_back( (edge){to, cap, (int)graph[to].size(), false, idx}); graph[to].emplace_back( (edge){from, 0, (int)graph[from].size() - 1, true, idx}); } bool build_augment_path(int s, int t) { min_cost.assign(graph.size(), -1); queue que; min_cost[s] = 0; que.push(s); while (!que.empty() && min_cost[t] == -1) { int p = que.front(); que.pop(); for (auto& e : graph[p]) { if (e.cap > 0 && min_cost[e.to] == -1) { min_cost[e.to] = min_cost[p] + 1; que.push(e.to); } } } return min_cost[t] != -1; } flow_t find_min_dist_augment_path(int idx, const int t, flow_t flow) { if (idx == t) return flow; for (int& i = iter[idx]; i < (int)graph[idx].size(); i++) { edge& e = graph[idx][i]; if (e.cap > 0 && min_cost[idx] < min_cost[e.to]) { flow_t d = find_min_dist_augment_path(e.to, t, min(flow, e.cap)); if (d > 0) { e.cap -= d; graph[e.to][e.rev].cap += d; return d; } } } return 0; } flow_t max_flow(int s, int t) { flow_t flow = 0; while (build_augment_path(s, t)) { iter.assign(graph.size(), 0); flow_t f; while ((f = find_min_dist_augment_path(s, t, INF)) > 0) flow += f; } return flow; } void output() { for (int i = 0; i < graph.size(); i++) { for (auto& e : graph[i]) { if (e.isrev) continue; auto& rev_e = graph[e.to][e.rev]; cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } } vector min_cut(int s) { // 何に使うのこれ? vector used(graph.size()); queue que; que.emplace(s); used[s] = true; while (not que.empty()) { int p = que.front(); que.pop(); for (auto& e : graph[p]) { if (e.cap > 0 and not used[e.to]) { used[e.to] = true; que.emplace(e.to); } } } return used; } }; void solve() { ll W; cin >> W; ll N; cin >> N; vc Js(N); rep(i, N) cin >> Js[i]; ll M; cin >> M; vc Cs(M); rep(i, M) cin >> Cs[i]; Dinic dinic(N + M + 2); rep(i, N) { dinic.add_edge(N + M, i, Js[i]); } rep(i, M) { ll Q; cin >> Q; unordered_set cant; rep(_, Q) { ll x; cin >> x; x--; cant.insert(x); } rep(j, N) { if (cant.count(j)) continue; dinic.add_edge(j, N + i, Js[j]); } dinic.add_edge(N + i, N + M + 1, Cs[i]); } ll f = dinic.max_flow(N + M, N + M + 1); dbg(f); if (f >= W) { print("SHIROBAKO"); } else { print("BANSAKUTSUKITA"); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); // ll T; cin >> T; // rep(_, T) solve(); }