結果
問題 |
No.3173 じゃんけんの勝ちの回数
|
ユーザー |
![]() |
提出日時 | 2025-06-06 21:33:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,824 bytes |
コンパイル時間 | 2,282 ms |
コンパイル使用メモリ | 207,116 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-06-06 21:33:07 |
合計ジャッジ時間 | 4,457 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; /* #include <atcoder/all> using namespace atcoder; */ #define rep(i,n) for(int i=0;i<n;i++) #define Rep(i,a,b) for(int i=a;i<b;i++) #define ALL(x) (x).begin(),(x).end() #define dbgv(x); for(auto now : x) cout << now << " "; cout << endl; //using P = pair<int,int>; using ll = long long; using ull = unsigned long long; //*/ template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<int> vint; const int INF=1001001001; int a[3],b[3]; //FordFulkerson<type> g(n);で初期化 //g.add_edge(a, b, c);でa->bに重みcの辺を張る //g.max_flow(s,t);でs->tでの最大流 template< typename flow_t > struct FordFulkerson { struct edge { int to; flow_t cap; int rev; bool isrev; int idx; }; vector< vector< edge > > graph; vector< int > used; const flow_t INF; int timestamp; FordFulkerson(int n) : INF(numeric_limits< flow_t >::max()), timestamp(0) { graph.resize(n); used.assign(n, -1); } void add_edge(int from, int to, flow_t cap, int idx = -1) { 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}); } flow_t dfs(int idx, const int t, flow_t flow) { if(idx == t) return flow; used[idx] = timestamp; for(auto &e : graph[idx]) { if(e.cap > 0 && used[e.to] != timestamp) { flow_t d = dfs(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; for(flow_t f; (f = dfs(s, t, INF)) > 0; timestamp++) { 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; } } } }; void solve(){ rep(i,3) cin >> a[i]; rep(i,3) cin >> b[i]; int n = a[0] + a[1] + a[2]; FordFulkerson<int> g(8); rep(i,3) g.add_edge(6,i,a[i]); rep(i,3) g.add_edge(i+3,7,b[i]); rep(i,3)rep(j,3)if((i+1)%3 != j) g.add_edge(i,j+3,1001001001); int mx = g.max_flow(6,7); cout << n-mx << " "; int mn = 0; rep(i,3)rep(j,3)if((i+1)%3 == j) mn += min(a[i],b[j]); cout << mn << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; cin >> t; rep(i,t) solve(); }