結果
| 問題 | No.1467 Selling Cars |
| ユーザー |
 kimiyuki
|
| 提出日時 | 2021-04-02 23:39:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,985 bytes |
| コンパイル時間 | 2,676 ms |
| コンパイル使用メモリ | 223,504 KB |
| 実行使用メモリ | 15,488 KB |
| 最終ジャッジ日時 | 2024-06-06 08:41:41 |
| 合計ジャッジ時間 | 13,059 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
ソースコード
#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;
}