結果
| 問題 | No.3509 Get More Money |
| コンテスト | |
| ユーザー |
 cho435
|
| 提出日時 | 2026-04-18 18:12:58 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 14,516 bytes |
| 記録 | |
| コンパイル時間 | 6,048 ms |
| コンパイル使用メモリ | 423,300 KB |
| 実行使用メモリ | 83,480 KB |
| 最終ジャッジ日時 | 2026-04-18 18:14:13 |
| 合計ジャッジ時間 | 16,777 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 59 |
ソースコード
#pragma GCC target("prefer-vector-width=512")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
// https://maspypy.github.io/library/flow/bflow.hpp
namespace maspy {
template <class Flow, class Cost>
struct MinCostFlow {
private:
static constexpr int SCALING_FACTOR = 2;
using V_id = uint32_t;
using E_id = uint32_t;
struct Edge {
friend struct MinCostFlow;
private:
V_id frm, to;
Flow flow, cap;
Cost cost;
E_id rev;
public:
Edge() = default;
Edge(const V_id frm_,
const V_id to_,
const Flow cap_,
const Cost cost_,
const E_id rev_)
: frm(frm_), to(to_), flow(0), cap(cap_), cost(cost_), rev(rev_) {};
[[nodiscard]] Flow residual_cap() const {
return cap - flow;
}
};
public:
struct EdgePtr {
friend struct MinCostFlow;
private:
const MinCostFlow* instance;
const V_id v;
const E_id e;
EdgePtr(const MinCostFlow* instance_, const V_id v_, const E_id e_)
: instance(instance_), v(v_), e(e_) {};
[[nodiscard]] const Edge& edge() const {
return instance->g[v][e];
}
[[nodiscard]] const Edge& rev() const {
const Edge& te = edge();
return instance->g[te.to][te.rev];
}
public:
[[nodiscard]] V_id frm() const {
return rev().to;
}
[[nodiscard]] V_id to() const {
return edge().to;
}
[[nodiscard]] Flow flow() const {
return edge().flow;
}
[[nodiscard]] Flow lower() const {
return -rev().cap;
}
[[nodiscard]] Flow upper() const {
return edge().cap;
}
[[nodiscard]] Cost cost() const {
return edge().cost;
}
[[nodiscard]] Cost gain() const {
return -edge().cost;
}
};
private:
V_id n;
std::vector<std::vector<Edge>> g;
std::vector<Flow> b;
public:
MinCostFlow(int n_) : n(n_) {
g.resize(n);
b.resize(n);
}
V_id add_vertex() {
++n;
g.resize(n);
b.resize(n);
return n - 1;
}
std::vector<V_id> add_vertices(const size_t size) {
std::vector<V_id> ret;
for (V_id i = 0; i < size; ++i) ret.emplace_back(n + i);
n += size;
g.resize(n);
b.resize(n);
return ret;
}
void add_edge(const V_id frm,
const V_id to,
const Flow lo,
const Flow hi,
const Cost cost) {
const E_id e = g[frm].size(), re = frm == to ? e + 1 : g[to].size();
assert(lo <= hi);
g[frm].emplace_back(Edge{frm, to, hi, cost, re});
g[to].emplace_back(Edge{to, frm, -lo, -cost, e});
edges.emplace_back(EdgePtr{this, frm, e});
}
void add_source(const V_id v, const Flow amount) {
b[v] += amount;
}
void add_sink(const V_id v, const Flow amount) {
b[v] -= amount;
}
private:
static Cost constexpr unreachable = std::numeric_limits<Cost>::max();
Cost farthest;
std::vector<Cost> potential, dist;
std::vector<Edge*> parent;
std::priority_queue<std::pair<Cost, int>,
std::vector<std::pair<Cost, int>>,
std::greater<std::pair<Cost, int>>>
pq;
std::vector<V_id> excess_vs, deficit_vs;
std::vector<EdgePtr> edges;
Edge& rev(const Edge& e) {
return g[e.to][e.rev];
}
void push(Edge& e, const Flow amount) {
e.flow += amount;
g[e.to][e.rev].flow -= amount;
}
Cost residual_cost(const V_id frm, const V_id to, const Edge& e) {
return e.cost + potential[frm] - potential[to];
}
bool dual(const Flow delta) {
dist.assign(n, unreachable);
parent.assign(n, nullptr);
excess_vs.erase(remove_if(begin(excess_vs), end(excess_vs),
[&](const V_id v) {
return b[v] < delta;
}),
end(excess_vs));
deficit_vs.erase(remove_if(begin(deficit_vs), end(deficit_vs),
[&](const V_id v) {
return b[v] > -delta;
}),
end(deficit_vs));
for (const auto v : excess_vs) pq.emplace(dist[v] = 0, v);
farthest = 0;
size_t deficit_count = 0;
while (!pq.empty()) {
const auto [d, u] = pq.top();
pq.pop();
if (dist[u] < d) continue;
farthest = d;
if (b[u] <= -delta) ++deficit_count;
if (deficit_count >= deficit_vs.size()) break;
for (auto& e : g[u]) {
if (e.residual_cap() < delta) continue;
const auto v = e.to;
const auto new_dist = d + residual_cost(u, v, e);
if (new_dist >= dist[v]) continue;
pq.emplace(dist[v] = new_dist, v);
parent[v] = &e;
}
}
pq = decltype(pq)();
for (V_id v = 0; v < n; ++v) {
potential[v] += std::min(dist[v], farthest);
}
return deficit_count > 0;
}
void primal(const Flow delta) {
for (const auto t : deficit_vs) {
if (dist[t] > farthest) continue;
Flow f = -b[t];
V_id v;
for (v = t; parent[v] != nullptr && f >= delta;
v = parent[v]->frm) {
f = std::min(f, parent[v]->residual_cap());
}
f = std::min(f, b[v]);
if (f < delta) continue;
for (v = t; parent[v] != nullptr;) {
auto& e = *parent[v];
push(e, f);
const size_t u = parent[v]->frm;
parent[v] = nullptr;
v = u;
}
b[t] += f;
b[v] -= f;
}
}
void saturate_negative(const Flow delta) {
excess_vs.clear();
deficit_vs.clear();
for (auto& es : g)
for (auto& e : es) {
const Flow rcap = e.residual_cap();
const Cost rcost = residual_cost(e.frm, e.to, e);
if (rcost < 0 && rcap >= delta) {
push(e, rcap);
b[e.frm] -= rcap;
b[e.to] += rcap;
}
}
for (V_id v = 0; v < n; ++v)
if (b[v] != 0) {
(b[v] > 0 ? excess_vs : deficit_vs).emplace_back(v);
}
}
public:
template <typename T>
std::pair<bool, T> solve() {
potential.resize(n);
for (auto& es : g)
for (auto& e : es) {
const Flow rcap = e.residual_cap();
if (rcap < 0) {
push(e, rcap);
b[e.frm] -= rcap;
b[e.to] += rcap;
}
}
Flow inf_flow = 1;
for (const auto& es : g)
for (const auto& e : es)
inf_flow = std::max(inf_flow, e.residual_cap());
Flow delta = 1;
while (delta <= inf_flow) delta *= SCALING_FACTOR;
for (delta /= SCALING_FACTOR; delta; delta /= SCALING_FACTOR) {
saturate_negative(delta);
while (dual(delta)) primal(delta);
}
T value = 0;
for (const auto& es : g)
for (const auto& e : es) {
value += T(e.flow) * e.cost;
}
value /= 2;
if (excess_vs.empty() && deficit_vs.empty()) {
return {true, value};
} else {
return {false, value};
}
}
template <class T>
T get_result_value() {
T value = 0;
for (const auto& es : g)
for (const auto& e : es) {
value += (T)(e.flow) * (T)(e.cost);
}
value /= (T)2;
return value;
}
std::vector<Cost> get_potential() {
std::fill(potential.begin(), potential.end(), 0);
for (int i = 0; i < (int)n; i++)
for (const auto& es : g)
for (const auto& e : es)
if (e.residual_cap() > 0)
potential[e.to] = std::min(potential[e.to],
potential[e.frm] + e.cost);
return potential;
}
std::vector<EdgePtr> get_edges() {
return edges;
}
};
} // namespace maspy
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
return x < y ? (x = y, true) : false;
}
// https://github.com/drken1215/algorithm/blob/master/GraphNetworkFlow/min_cost_b_flow_by_network_simplex_method.cpp
// Network Simplex Method
template <class FLOW, class COST> struct NetworkSimplex {
struct Edge {
int from, to;
FLOW cap;
COST cost;
friend ostream& operator<<(ostream& s, const Edge& e) {
return s << e.from << " -> " << e.to << " (" << e.cap << ", "
<< e.cost << ")";
}
};
struct Parent {
int p, e;
FLOW up, down;
};
// inner values
int N, M;
vector<Edge> edges;
vector<FLOW> lowers; // for edge i
vector<FLOW> dss; // for node v (demand and supply)
// intermediate results
int BUCKET_SIZE, MINOR_LIMIT;
vector<Parent> parents;
vector<int> depth, nex, pre, candidates;
// results
bool feasible;
COST total_cost;
vector<FLOW> flows;
vector<COST> pots;
// constructor
explicit NetworkSimplex(int n = 0) : N(n), dss(n) {
}
// debugger
friend ostream& operator<<(ostream& s, const NetworkSimplex& ns) {
s << "feasibility: " << (ns.feasible ? "true" : "false") << '\n';
s << "optimal value: " << ns.total_cost << '\n';
for (int i = 0; i < ns.M; i += 2) {
auto e = ns.edges[i];
s << e.from << " -> " << e.to << ": " << ns.flows[i / 2]
<< " (remained cap: " << e.cap << ", cost: " << e.cost << ")\n";
}
for (int v = 0; v < ns.N; v++)
cout << "node " << v << ": " << ns.pots[v] << '\n';
return s;
}
// setter
void add_edge(int from, int to, FLOW lower, FLOW upper, COST cost) {
edges.push_back({from, to, upper - lower, cost});
edges.push_back({to, from, 0, -cost});
lowers.push_back(lower);
dss[from] -= lower;
dss[to] += lower;
M = (int)edges.size();
}
void add_ds(int v, FLOW ds) {
assert(v >= 0 && v < N);
dss[v] += ds;
}
// solver
pair<bool, COST> solve() {
BUCKET_SIZE = max(int(sqrt(double(M)) * 0.2), 10);
MINOR_LIMIT = max(int(BUCKET_SIZE * 0.1), 3);
precompute();
candidates.reserve(BUCKET_SIZE);
int ei = 0;
while (true) {
for (int i = 0; i < MINOR_LIMIT; i++)
if (!minor()) break;
COST best = 0;
int best_ei = -1;
candidates.clear();
for (int i = 0; i < (int)edges.size(); i++) {
if (edges[ei].cap) {
COST clen = edges[ei].cost + pots[edges[ei ^ 1].to] -
pots[edges[ei].to];
if (clen < 0) {
if (clen < best) best = clen, best_ei = ei;
candidates.push_back(ei);
if ((int)candidates.size() == BUCKET_SIZE) break;
}
}
ei++;
if (ei == (int)edges.size()) ei = 0;
}
if (candidates.empty()) break;
push_flow(best_ei);
}
if (!postcompute()) return {false, COST(-1)};
else return {true, total_cost};
}
void connect(int a, int b) {
nex[a] = b, pre[b] = a;
}
void precompute() {
pots.assign(N + 1, 0);
parents.resize(N), depth.assign(N + 1, 1);
nex.assign((N + 1) * 2, 0), pre.assign((N + 1) * 2, 0);
COST inf_cost = 1;
for (int i = 0; i < M; i += 2) {
inf_cost += (edges[i].cost >= 0 ? edges[i].cost : -edges[i].cost);
}
edges.reserve(M + N * 2);
for (int i = 0; i < N; i++) {
if (dss[i] >= 0) {
edges.push_back({i, N, 0, inf_cost});
edges.push_back({N, i, dss[i], -inf_cost});
pots[i] = -inf_cost;
} else {
edges.push_back({i, N, -dss[i], -inf_cost});
edges.push_back({N, i, 0, inf_cost});
pots[i] = inf_cost;
}
int e = (int)edges.size() - 2;
parents[i] = {N, e, edges[e].cap, edges[e ^ 1].cap};
}
depth[N] = 0;
for (int i = 0; i < N + 1; i++) connect(i * 2, i * 2 + 1);
for (int i = 0; i < N; i++)
connect(i * 2 + 1, nex[N * 2]), connect(N * 2, i * 2);
}
bool postcompute() {
for (int i = 0; i < N; i++) {
edges[parents[i].e].cap = parents[i].up;
edges[parents[i].e ^ 1].cap = parents[i].down;
}
feasible = true;
for (int i = 0; i < N; i++) {
if (dss[i] >= 0) {
if (edges[M + i * 2 + 1].cap) feasible = false;
} else {
if (edges[M + i * 2].cap) feasible = false;
}
}
if (!feasible) return false;
total_cost = 0;
flows.clear();
for (int i = 0; i < M; i += 2) {
flows.push_back(lowers[i / 2] + edges[i ^ 1].cap);
total_cost += flows.back() * edges[i].cost;
}
pots.pop_back();
return true;
}
void push_flow(int ei0) {
int u0 = edges[ei0 ^ 1].to, v0 = edges[ei0].to, del_u = v0;
FLOW flow = edges[ei0].cap;
COST clen = edges[ei0].cost + pots[u0] - pots[v0];
bool del_u_side = true;
int lca = get_lca(u0, v0, flow, del_u_side, del_u);
if (flow) {
int u = u0, v = v0;
while (u != lca)
parents[u].up += flow, parents[u].down -= flow,
u = parents[u].p;
while (v != lca)
parents[v].up -= flow, parents[v].down += flow,
v = parents[v].p;
}
int u = u0, par = v0;
auto p_caps =
make_pair(edges[ei0].cap - flow, edges[ei0 ^ 1].cap + flow);
COST p_diff = -clen;
if (!del_u_side) {
swap(u, par);
swap(p_caps.first, p_caps.second);
p_diff *= -1;
}
int par_e = ei0 ^ (del_u_side ? 0 : 1);
while (par != del_u) {
int d = depth[par], idx = u * 2;
while (idx != u * 2 + 1) {
if (idx % 2 == 0)
d++, pots[idx / 2] += p_diff, depth[idx / 2] = d;
else d--;
idx = nex[idx];
}
connect(pre[u * 2], nex[u * 2 + 1]);
connect(u * 2 + 1, nex[par * 2]);
connect(par * 2, u * 2);
swap(parents[u].e, par_e);
par_e ^= 1;
swap(parents[u].up, p_caps.first);
swap(parents[u].down, p_caps.second);
swap(p_caps.first, p_caps.second);
int next_u = parents[u].p;
parents[u].p = par;
par = u;
u = next_u;
}
edges[par_e].cap = p_caps.first;
edges[par_e ^ 1].cap = p_caps.second;
}
bool minor() {
if (candidates.empty()) return false;
COST best = 0;
int best_ei = -1;
int i = 0;
while (i < int(candidates.size())) {
int ei = candidates[i];
if (!edges[ei].cap) {
swap(candidates[i], candidates.back());
candidates.pop_back();
continue;
}
COST clen =
edges[ei].cost + pots[edges[ei ^ 1].to] - pots[edges[ei].to];
if (clen >= 0) {
swap(candidates[i], candidates.back());
candidates.pop_back();
continue;
}
if (clen < best) best = clen, best_ei = ei;
i++;
}
if (best_ei == -1) return false;
push_flow(best_ei);
return true;
}
int get_lca(int u, int v, FLOW& flow, bool& del_u_side, int& del_u) {
auto up_u = [&]() {
if (parents[u].down < flow)
flow = parents[u].down, del_u = u, del_u_side = true;
u = parents[u].p;
};
auto up_v = [&]() {
if (parents[v].up <= flow)
flow = parents[v].up, del_u = v, del_u_side = false;
v = parents[v].p;
};
if (depth[u] >= depth[v]) {
int num = depth[u] - depth[v];
for (int i = 0; i < num; i++) up_u();
} else {
int num = depth[v] - depth[u];
for (int i = 0; i < num; i++) up_v();
}
while (u != v) up_u(), up_v();
return u;
}
};
void solve() {
ll n, k;
cin >> n >> k;
vector<int> a(n), b(n), c(n), d(n);
rep(i, 0, n) cin >> a[i];
rep(i, 0, n) cin >> b[i];
rep(i, 0, n) cin >> c[i];
rep(i, 0, n) cin >> d[i];
// maspy::MinCostFlow<ll, ll> mcf(n + 1);
NetworkSimplex<ll, ll> mcf(n + 1);
rep(i, 0, n) {
mcf.add_edge(n, i, 0, b[i], a[i]);
}
rep(i, 0, n - 1) {
mcf.add_edge(i, i + 1, 0, k, 0);
}
rep(i, 0, n) {
mcf.add_edge(i, n, 0, d[i], -c[i]);
}
auto [f, ans] = mcf.solve();
assert(f);
cout << -ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int t = 1;
cin >> t;
while (t--) solve();
}