結果

問題 No.2309 [Cherry 5th Tune D] 夏の先取り
ユーザー hongrockhongrock
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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]>>1
using 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0