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

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 22:48:00
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,471 bytes
• コンパイル時間: 3,980 ms
• コンパイル使用メモリ: 346,292 KB
• 実行使用メモリ: 64,408 KB
• 最終ジャッジ日時: 2026-04-18 22:49:52
• 合計ジャッジ時間: 14,152 ms
• ジャッジサーバーID （参考情報）: judge3_1 / 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), 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);
     }

     long long min_cost_profit_flow(int s, int t) {
         const long long INF = (1LL<<62);

         long long maxcap = 0;
         for (int v=0; v<N; v++)
             for (auto &e: g[v]) maxcap = max(maxcap, e.cap);

         long long delta = 1;
         while (delta <= maxcap) delta <<= 1;
         delta >>= 1;

         long long total_cost = 0;

         while (delta > 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 < delta) 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;

                 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;
                 }
                 total_cost += addf * shortest;
             }
             delta >>= 1;
         }
         return total_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, 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
         }

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