結果

問題 No.1467 Selling Cars
ユーザー kimiyuki
提出日時 2021-04-02 23:39:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,985 bytes
コンパイル時間 2,415 ms
コンパイル使用メモリ 216,620 KB
最終ジャッジ日時 2025-01-20 10:08:27
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

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

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 2 "/home/user/Library/utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 7 "/home/user/Library/graph/minimum-cost-flow.hpp"
namespace min_cost_flow {
template <class T>
struct edge { int to; T cap, cost; int rev; };
template <class T>
void add_edge(std::vector<std::vector<edge<T> > > & graph, int from, int to, T cap, T cost) {
    graph[from].push_back((edge<T>) {   to, cap,  cost, int(graph[  to].size())     });
    graph[  to].push_back((edge<T>) { from,  0, - cost, int(graph[from].size()) - 1 });
}
template <class T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
/**
 * @brief 最小費用流 (primal-dual)
 * @note mainly $O(V^2 U C)$ for U is the sum of capacities and $C$ is the sum of costs. and additional $O(V E)$ if negative edges exist
 */
template <class T>
T run_destructive(std::vector<std::vector<edge<T> > > & graph, int src, int dst, T flow) {
    T result = 0;
    std::vector<T> potential(graph.size());
    if (0 < flow) {  // initialize potential when negative edges exist (slow). you can remove this if unnecessary
        std::fill(ALL(potential), std::numeric_limits<T>::max());
        potential[src] = 0;
        while (true) {  // Bellman-Ford algorithm
            bool updated = false;
            REP (e_from, graph.size()) for (auto & e : graph[e_from]) if (e.cap) {
                if (potential[e_from] == std::numeric_limits<T>::max()) continue;
                if (potential[e.to] > potential[e_from] + e.cost) {
                    potential[e.to] = potential[e_from] + e.cost;  // min
                    updated = true;
                }
            }
            if (not updated) break;
        }
    }
    while (0 < flow) {
        // update potential using dijkstra
        std::vector<T> distance(graph.size(), std::numeric_limits<T>::max());  // minimum distance
        std::vector<int> prev_v(graph.size());  // constitute a single-linked-list represents the flow-path
        std::vector<int> prev_e(graph.size());
        {  // initialize distance and prev_{v,e}
            reversed_priority_queue<std::pair<T, int> > que;  // distance * vertex
            distance[src] = 0;
            que.emplace(0, src);
            while (not que.empty()) {  // Dijkstra's algorithm
                T d; int v; std::tie(d, v) = que.top(); que.pop();
                if (potential[v] == std::numeric_limits<T>::max()) continue;  // for unreachable nodes
                if (distance[v] < d) continue;
                // look round the vertex
                REP (e_index, graph[v].size()) {
                    // consider updating
                    edge<T> e = graph[v][e_index];
                    int w = e.to;
                    if (potential[w] == std::numeric_limits<T>::max()) continue;
                    T d1 = distance[v] + e.cost + potential[v] - potential[w];  // updated distance
                    if (0 < e.cap and d1 < distance[e.to]) {
                        distance[w] = d1;
                        prev_v[w] = v;
                        prev_e[w] = e_index;
                        que.emplace(d1, w);
                    }
                }
            }
        }
        if (distance[dst] == std::numeric_limits<T>::max()) return -1;  // no such flow
        REP (v, graph.size()) {
            if (potential[v] == std::numeric_limits<T>::max()) continue;
            potential[v] += distance[v];
        }
        // finish updating the potential
        // let flow on the src->dst minimum path
        T delta = flow; // capacity of the path
        for (int v = dst; v != src; v = prev_v[v]) {
            delta = std::min(delta, graph[prev_v[v]][prev_e[v]].cap);
        }
        flow -= delta;
        result += delta * potential[dst];
        for (int v = dst; v != src; v = prev_v[v]) {
            edge<T> & e = graph[prev_v[v]][prev_e[v]];  // reference
            e.cap -= delta;
            graph[v][e.rev].cap += delta;
        }
    }
    return result;
}
}
#line 4 "main.cpp"
using namespace std;
vector<int64_t> solve(int m, int n, const vector<int64_t>& a, const vector<int64_t>& b) {
    // coordinate compression
    vector<int> points;
    points.insert(points.end(), ALL(a));
    points.insert(points.end(), ALL(b));
    sort(ALL(points));
    points.erase(unique(ALL(points)), points.end());
    auto lookup = [&](int x) -> int {
        return lower_bound(ALL(points), x) - points.begin();
    };
    int src = points.size();
    int dst = points.size() + 1;
    vector<int64_t> ans(m);
    REP (k, m) {
        std::vector<std::vector<min_cost_flow::edge<int64_t> > > g(points.size() + 2);
        REP (i, m) {
            min_cost_flow::add_edge<int64_t>(g, src, lookup(a[i]), 1, 0);
        }
        REP (i, (int)points.size() - 1) {
            int64_t delta = points[i + 1] - points[i];
            min_cost_flow::add_edge<int64_t>(g, i, i + 1, m, delta);
            min_cost_flow::add_edge<int64_t>(g, i + 1, i, m, delta);
        }
        REP (j, n) {
            min_cost_flow::add_edge<int64_t>(g, lookup(b[j]), dst, k + 1, 0);
        }
        ans[k] = min_cost_flow::run_destructive<int64_t>(g, src, dst, m);
    }
    return ans;
}
// generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    constexpr char endl = '\n';
    int M, N;
    cin >> M;
    vector<int64_t> A(M);
    cin >> N;
    vector<int64_t> B(N);
    REP (i, M) { cin >> A[i]; }
    REP (i, N) { cin >> B[i]; }
    auto ans = solve(M, N, A, B);
    REP (i, M) { cout << ans[i] << endl; }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0