#1160118 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 22:33:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,258 bytes
• コンパイル時間: 2,490 ms
• コンパイル使用メモリ: 346,292 KB
• 実行使用メモリ: 70,696 KB
• 最終ジャッジ日時: 2026-04-18 22:34:05
• 合計ジャッジ時間: 13,219 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge2_0

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 59

ソースコード

#include <bits/stdc++.h>
 using namespace std;

 struct MinCostFlow {
     struct Edge {
         int to, rev;
         long long cap, cost;
     };
     int N;
     vector<vector<Edge>> g;
     vector<long long> pot, dist;
     vector<int> pv_v, pv_e;

     MinCostFlow(int n): N(n), g(n), pot(n, 0), dist(n), pv_v(n), pv_e(n) {}

     void add_edge(int fr, int to, long long cap, long long cost) {
         Edge a{to, (int)g[to].size(), cap, cost};
         Edge b{fr, (int)g[fr].size(), 0, -cost};
         g[fr].push_back(a);
         g[to].push_back(b);
     }

     // Returns total (flow, cost). We stop when shortest path cost >= 0.
     pair<long long,long long> min_cost_profit_flow(int s, int t) {
         const long long INF = (1LL<<62);
         long long flow = 0, cost = 0;

         while (true) {
             fill(dist.begin(), dist.end(), INF);
             dist[s] = 0;
             priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
             pq.push({0, s});

             while (!pq.empty()) {
                 auto [d, v] = pq.top(); pq.pop();
                 if (d != dist[v]) continue;
                 for (int i=0;i<(int)g[v].size();i++) {
                     Edge &e = g[v][i];
                     if (e.cap <= 0) continue;
                     long long nd = d + e.cost + pot[v] - pot[e.to];
                     if (nd < dist[e.to]) {
                         dist[e.to] = nd;
                         pv_v[e.to] = v;
                         pv_e[e.to] = i;
                         pq.push({nd, e.to});
                     }
                 }
             }

             if (dist[t] == INF) break;
             long long shortest = dist[t] + pot[t] - pot[s];
             if (shortest >= 0) break; // no more profit

             for (int v=0; v<N; v++) if (dist[v] < INF) pot[v] += dist[v];

             long long addf = LLONG_MAX;
             for (int v=t; v!=s; v=pv_v[v]) {
                 Edge &e = g[pv_v[v]][pv_e[v]];
                 addf = min(addf, e.cap);
             }
             for (int v=t; v!=s; v=pv_v[v]) {
                 Edge &e = g[pv_v[v]][pv_e[v]];
                 e.cap -= addf;
                 g[v][e.rev].cap += addf;
             }
             flow += addf;
             cost += addf * shortest;
         }
         return {flow, cost};
     }
 };

 int main() {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);

     int T;
     cin >> T;
     while (T--) {
         int N;
         long long K;
         cin >> N >> K;
         vector<long long> A(N+1), B(N+1), C(N+1), D(N+1);
         for (int i=1;i<=N;i++) cin >> A[i];
         for (int i=1;i<=N;i++) cin >> B[i];
         for (int i=1;i<=N;i++) cin >> C[i];
         for (int i=1;i<=N;i++) cin >> D[i];

         int S = 0;
         int Tnode = N + 1;
         MinCostFlow mcf(N + 2);

         for (int i=1;i<=N;i++) {
             mcf.add_edge(S, i, B[i], A[i]);      // buy
             mcf.add_edge(i, Tnode, D[i], -C[i]); // sell
             if (i < N) mcf.add_edge(i, i+1, K, 0); // store
         }

         auto [flow, cost] = mcf.min_cost_profit_flow(S, Tnode);
         long long profit = -cost;
         cout << profit << "\n";
     }
     return 0;
 }