#include "roads.h" #include <vector> using namespace std; typedef vector<int> vi; typedef vector<long long> vl; long long max(long long a, long long b) { return a > b ? a : b; } const int N = 100000; unsigned int X = 12345; int rand_() { return (X *= 3) >> 1; } void sort(int *ww, int l, int r) { while (l < r) { int i = l, j = l, k = r, w = ww[l + rand_() % (r - l)], tmp; while (j < k) if (ww[j] == w) j++; else if (ww[j] < w) { tmp = ww[i], ww[i] = ww[j], ww[j] = tmp; i++, j++; } else { k--; tmp = ww[j], ww[j] = ww[k], ww[k] = tmp; } sort(ww, l, i); l = k; } } int ww[N - 1]; vl minimum_closure_costs(int n, vi uu, vi vv, vi ww_) { vl ans(n); int h; for (h = 0; h < n - 1; h++) ww[h] = ww_[h]; if (n <= 2 || uu[1] == 0) { sort(ww, 0, n - 1); for (h = n - 1; h >= 0; h--) ans[h] = h == n - 1 ? 0 : ans[h + 1] + ww[n - 2 - h]; } else { long long dp, dq, dp_, dq_; for (h = 0; h < n; h++) ans[h] = 0; for (h = 0; h < n - 1; h++) ans[0] += ww[h]; dp = ww[0], dq = 0; for (h = 1; h < n - 1; h++) dp_ = dq + ww[h], dq_ = max(dp, dq), dp = dp_, dq = dq_; ans[1] = ans[0] - max(dp, dq); } return ans; }