結果
問題 | No.177 制作進行の宮森あおいです! |
ユーザー | momoyuu |
提出日時 | 2022-09-30 22:41:00 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 3,045 bytes |
コンパイル時間 | 3,237 ms |
コンパイル使用メモリ | 259,580 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-02 06:15:08 |
合計ジャッジ時間 | 3,962 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 4 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 11 ms
6,944 KB |
testcase_10 | AC | 16 ms
6,940 KB |
testcase_11 | AC | 15 ms
6,940 KB |
testcase_12 | AC | 9 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; template<class t> using vc = vector<t>; template<class t> using vvc = vc<vc<t>>; using pi = pair<int,int>; using pl = pair<ll,ll>; using vi = vc<int>; using vvi = vvc<int>; using vl = vc<ll>; using vvl = vvc<ll>; #define rep(i,a,b) for (int i = (int)(a); i < (int)(b); i++) #define irep(i,a,b) for (int i = (int)(a); i > (int)(b); i--) #define all(a) a.begin(),a.end() #define print(n) cout << n << '\n' #define pritn(n) print(n) #define printv(n,a) {copy(all(n),ostream_iterator<a>(cout," ")); cout<<"\n";} #define printvv(n,a) {for(auto itr:n) printv(itr,a);} #define rup(a,b) (a+b-1)/b #define input(A,N) rep(i,0,N) cin>>A[i] #define chmax(a,b) a = max(a,b) #define chmin(a,b) a = min(a,b) template< typename T > struct edge{ int from,to,rev; T cost; /* *to:繋がってる先 *cost:辺のコスト */ edge(int from,int to,int rev,T cost):from(from),to(to),rev(rev),cost(cost){}; edge &operator=(const int& x){ to = x; return *this; } }; template< typename T > struct graph{ int n; vector<vector<edge<T>>> e; graph(int n):n(n),e(n){} void addedge(int from,int to,T cost){ e[from].emplace_back(from,to,(int)e[to].size(),cost); e[to].emplace_back(to,from,(int)e[from].size()-1,0); } vector<edge<T>> &operator[](int i) { return e[i]; } }; template< typename T > struct FordFulkerson{ const int INF = (T)1e9; vector<int> vis; FordFulkerson(){}; T dfs(graph<T>&g,int ni,int t,T f){ if(ni==t) return f; vis[ni] = 1; for(auto &e:g[ni]){ if(vis[e.to]||e.cost<=0) continue; T d = dfs(g,e.to,t,min(f,e.cost)); if(d>0){ e.cost -= d; g[e.to][e.rev].cost += d; return d; } } return 0; } //start:s->to:t T max_flow(graph<T>&g,int s,int t){ T flow = 0; while(1){ vis.assign(g.n,0); T d = dfs(g,s,t,INF); if(d==0){ return flow; }else{ flow += d; } } return 0; } }; int main(){ cout << fixed << setprecision(15); int w; cin>>w; int n; cin>>n; vi j(n); input(j,n); int m; cin>>m; vi c(m); input(c,m); vvi a(n,vi(m,0)); rep(i,0,m){ int q; cin>>q; while(q--){ int x; cin>>x; x--; a[x][i] = 1; } } ll inf = (ll)1e12; graph<ll> g(n+m+2); rep(i,0,n)g.addedge(n+m,i,j[i]); rep(i,0,m)g.addedge(i+n,n+m+1,c[i]); rep(i,0,n)rep(j,0,m){ if(a[i][j])continue; g.addedge(i,j+n,inf); } FordFulkerson<ll> f; ll can = f.max_flow(g,n+m,n+m+1); if(can>=w) print("SHIROBAKO"); else print("BANSAKUTSUKITA"); //system("pause"); return 0; }