結果
問題 | No.2309 [Cherry 5th Tune D] 夏の先取り |
ユーザー |
![]() |
提出日時 | 2023-05-19 23:25:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 538 ms / 3,000 ms |
コード長 | 2,875 bytes |
コンパイル時間 | 1,926 ms |
コンパイル使用メモリ | 204,456 KB |
最終ジャッジ日時 | 2025-02-13 03:08:32 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i, a, n) for(int i=(a); i<(n); ++i)#define per(i, a, n) for(int i=(a); i>(n); --i)#define pb emplace_back#define mp make_pair#define clr(a, b) memset(a, b, sizeof(a))#define all(x) (x).begin(),(x).end()#define lowbit(x) (x & -x)#define fi first#define se second#define lson o<<1#define rson o<<1|1#define gmid l[o]+r[o]>>1using ll = long long;using ull = unsigned long long;using pii = pair<int,int>;using pll = pair<ll, ll>;using ui = unsigned int;constexpr int mod = 998244353;constexpr int inf = 0x3f3f3f3f;constexpr ll infll = (ll)1e18;constexpr double EPS = 1e-8;const double PI = acos(-1.0);constexpr int N = 2e5 + 10;int T, a, b, c;ll x, y, z, w;int idx[10][10];struct Edge{int from, to, cap, flow;ll cost;Edge(){}Edge(int from, int to, int cap, ll cost):from(from),to(to),cap(cap),cost(cost){flow = 0;}};vector<Edge> G;vector<int> V[10];int A[10], P[10];ll d[10];bool inq[10];void add_edge(int from, int to){G.pb(from, to, 0, 0);G.pb(to, from, 0, 0);int x = G.size();idx[from][to] = x - 2;V[from].pb(x - 2);V[to].pb(x - 1);}void upd(int id, int cap, ll cost){G[id].cap = cap;G[id].cost = cost;G[id^1].cost = -cost;}bool BellmanFord(int &flow, ll &cost){rep(i, 1, 6){d[i] = infll;inq[i] = 0;}d[0] = 0;A[0] = inf;P[0] = -1;queue<int> Q;inq[0] = 1;Q.push(0);while(!Q.empty()){int x = Q.front(); Q.pop();inq[x] = 0;for(int y : V[x]){Edge &e = G[y];if(e.cap > e.flow && d[e.to] > d[x] + e.cost){d[e.to] = d[x] + e.cost;A[e.to] = min(A[x], e.cap - e.flow);P[e.to] = y;if(!inq[e.to]){inq[e.to] = 1;Q.push(e.to);}}}}if(d[5] == infll) return 0;flow += A[5];cost += A[5] * d[5];int x = 5;while(x){G[P[x]].flow += A[5];G[P[x]^1].flow -= A[5];x = G[P[x]].from;}return 1;}ll solve(int t){for(auto &e : G) e.flow = 0;upd(idx[0][1], a, 0);upd(idx[0][2], t, 0);upd(idx[1][3], b - t, -x);upd(idx[1][4], a, -z);upd(idx[2][4], t, -y);upd(idx[3][4], b - t, -w + x);upd(idx[1][5], a, 0);upd(idx[2][5], t, 0);upd(idx[3][5], b - t, 0);upd(idx[4][5], c, 0);int flow = 0;ll cost = 0;while(BellmanFord(flow, cost));return -cost;}void _main(){add_edge(0, 1);add_edge(0, 2);add_edge(1, 3);add_edge(1, 4);add_edge(2, 4);add_edge(3, 4);add_edge(1, 5);add_edge(2, 5);add_edge(3, 5);add_edge(4, 5);cin >> T;while(T--){cin >> a >> b >> c;cin >> x >> y >> z >> w;ll ans = 0;rep(i, 0, b + 1){ans = max(ans, solve(i));}cout << ans << '\n';}}int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);_main();return 0;}