結果
| 問題 | No.177 制作進行の宮森あおいです！ |
| ユーザー |
 porkleoi
|
| 提出日時 | 2024-04-03 22:58:43 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 16 ms / 2,000 ms |
| コード長 | 4,850 bytes |
| コンパイル時間 | 3,052 ms |
| コンパイル使用メモリ | 257,940 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-01 00:08:51 |
| 合計ジャッジ時間 | 3,726 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define rep2(i, s, n) for (ll i = s; i <= (ll)(n); i++)#define rep3(i, s, n, d) for (ll i = s; i <= (ll)(n); i += d)#define rep4(i, s, n, d) for (ll i = s; i >= (ll)(n); i += d)typedef long long ll;typedef long double ld;typedef unsigned long long ull;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<vvi> vvvi;typedef vector<vvvi> vvvvi;typedef vector<string> vs;typedef vector<vs> vvs;typedef vector<vvs> vvvs;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<vvc> vvvc;typedef vector<ll> vll;typedef vector<vll> vvll;typedef vector<vvll> vvvll;typedef vector<vvvll> vvvvll;typedef vector<double> vd;typedef vector<vd> vvd;typedef vector<vvd> vvvd;typedef vector<ld> vld;typedef vector<vld> vvld;typedef vector<vvld> vvvld;typedef vector<bool> vb;typedef vector<vd> vvb;typedef vector<vvd> vvvb;typedef vector<pair<int, int>> vpi;typedef vector<pair<ll, ll>> vpll;typedef pair<int, int> pi;typedef vector<pi> vpi;typedef vector<vpi> vvpi;typedef pair<ll, ll> pll;typedef vector<pll> vpll;typedef vector<vpll> vvpll;typedef tuple<int, int, int> tui3;typedef tuple<ll, ll, ll> tull3;typedef priority_queue<int, vector<int>, greater<int>> pqi;typedef priority_queue<vi, vector<vi>, greater<vi>> pqvi;typedef priority_queue<ll, vector<ll>, greater<ll>> pqll;typedef priority_queue<vll, vector<vll>, greater<vll>> pqvll;typedef priority_queue<pll, vector<pll>, greater<pll>> pqpll;typedef priority_queue<pll, vector<pll>, less<pll>> rpqpll;typedef priority_queue<int, vector<int>, less<int>> rpqi;typedef priority_queue<vi, vector<vi>, less<vi>> rpqvi;typedef priority_queue<tui3, vector<tui3>, greater<tui3>> pqtui3;typedef priority_queue<tui3, vector<tui3>, less<tui3>> rpqtui3;typedef priority_queue<tull3, vector<tull3>, greater<tull3>> pqtull3;typedef priority_queue<tull3, vector<tull3>, less<tull3>> rpqtull3;#define yes(ans) if(ans)cout << "yes"<< endl; else cout << "no" << endl#define Yes(ans) if(ans)cout << "Yes"<< endl; else cout << "No" << endl#define YES(ans) if(ans)cout << "YES"<< endl ;else cout << "NO" << endl#define printv(vec) {rep(i, vec.size()) cout << vec[i] << ' '; cout << endl;}#define printvv(vec) rep(i, vec.size()) {rep(j, vec[i].size()) cout << vec[i][j] << ' '; cout << endl;};#define printvvv(vec) rep(i, vec.size()) { rep(j, vec[i].size()) { rep(k, vec[i][j].size()) cout << vec[i][j][k] << ' '; cout << " "; }cout << endl;};#define all1(x) x.begin(),x.end()#define all2(x) x.rbegin(), x.rend()#define so(x) sort(all1(x))#define re(x) reverse(all1(x))#define rso(x) sort(all2(x))#define vco(x, a) count(all1(x), a)#define per(x) next_permutation(all1(x))#define iINF 2147483647#define llINF 9223372036854775807#define INF 1000000000000000000#define mod 998244353#define mod2 1000000007template <typename T>struct FordFulkerson{struct Edge{int to;T capacity;int reverse_index;};vector<vector<Edge>> graph;vi used;T inf;int time;FordFulkerson(int n) : graph(n), used(n, -1), inf(numeric_limits<T>::max()), time(0) {}void add_edge(int from, int to, ll capacity){graph[from].push_back({to, capacity, int(graph[to].size())});graph[to].push_back({from, 0, int(graph[from].size()-1)});}T dfs(int v, int sink, T flow){if(v==sink) return flow;used[v] = time;for(auto& edge:graph[v]){if(used[edge.to]!=time && edge.capacity>0){T d = dfs(edge.to, sink, min(flow, edge.capacity));if(d>0){edge.capacity -= d;graph[edge.to][edge.reverse_index].capacity += d;return d;}}}return 0;}T max_flow(int source, int sink){used.assign(used.size(), -1);T ans = 0;while(true){T f = dfs(source, sink, inf);if(f==0) break;ans += f;time++;}return ans;}};int main() {// アルゴリズム一覧を見る// 嘘解法ですかll w; cin >> w;int n; cin >> n;vll a(n); rep(i, n) cin >> a[i];int m; cin >> m;vll b(m); rep(i, m) cin >> b[i];FordFulkerson<ll> flow(n+m+2);rep(i, n) flow.add_edge(0, i+1, a[i]);rep(i, m) flow.add_edge(n+i+1, n+m+1, b[i]);rep(i, m){int q; cin >> q;vll flag(n);rep(j, q){int x; cin >> x;x--;flag[x] = 1;}rep(j, n){if(flag[j]) continue;flow.add_edge(j+1, n+i+1, a[j]);}}cout << (flow.max_flow(0, n+m+1)>=w ? "SHIROBAKO":"BANSAKUTSUKITA") << endl;}