結果

問題 No.1288 yuki collection
ユーザー 👑 hitonanodehitonanode
提出日時 2021-09-11 01:46:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 352 ms / 5,000 ms
コード長 13,287 bytes
コンパイル時間 1,497 ms
コンパイル使用メモリ 108,760 KB
実行使用メモリ 5,664 KB
最終ジャッジ日時 2023-09-03 18:48:29
合計ジャッジ時間 9,169 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,384 KB
testcase_12 AC 2 ms
4,384 KB
testcase_13 AC 231 ms
5,444 KB
testcase_14 AC 202 ms
5,444 KB
testcase_15 AC 142 ms
5,120 KB
testcase_16 AC 213 ms
5,120 KB
testcase_17 AC 184 ms
5,428 KB
testcase_18 AC 229 ms
5,356 KB
testcase_19 AC 207 ms
5,388 KB
testcase_20 AC 207 ms
5,488 KB
testcase_21 AC 115 ms
5,384 KB
testcase_22 AC 137 ms
5,388 KB
testcase_23 AC 136 ms
5,504 KB
testcase_24 AC 201 ms
5,384 KB
testcase_25 AC 205 ms
5,520 KB
testcase_26 AC 223 ms
5,380 KB
testcase_27 AC 213 ms
5,440 KB
testcase_28 AC 277 ms
5,440 KB
testcase_29 AC 272 ms
5,376 KB
testcase_30 AC 326 ms
5,384 KB
testcase_31 AC 329 ms
5,436 KB
testcase_32 AC 335 ms
5,384 KB
testcase_33 AC 111 ms
5,380 KB
testcase_34 AC 189 ms
5,388 KB
testcase_35 AC 220 ms
5,664 KB
testcase_36 AC 103 ms
5,396 KB
testcase_37 AC 142 ms
5,484 KB
testcase_38 AC 109 ms
5,388 KB
testcase_39 AC 111 ms
5,432 KB
testcase_40 AC 352 ms
5,488 KB
testcase_41 AC 1 ms
4,384 KB
testcase_42 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "combinatorial_opt/test/mincostflow.yuki1288.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1288"
#line 2 "combinatorial_opt/mincostflow_nonegativeloop.hpp"
#include <cassert>
#include <limits>
#include <queue>
#include <vector>

#include <array>
#include <limits>
#include <type_traits>
#include <utility>
#include <vector>

template <class Uint> class radix_heap_array {
    int sz;
    Uint last;
    std::array<std::vector<std::pair<Uint, int>>, std::numeric_limits<Uint>::digits + 1> v;

    struct smallpii {
        unsigned b : 7;
        int j : 25;
    };
    std::vector<smallpii> i2bj;

    template <class U, typename std::enable_if<sizeof(U) == 4>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 32 - __builtin_clz(x) : 0;
    }
    template <class U, typename std::enable_if<sizeof(U) == 8>::type * = nullptr>
    static inline unsigned bucket(U x) noexcept {
        return x ? 64 - __builtin_clzll(x) : 0;
    }

    void pull() {
        if (!v[0].empty()) return;
        int b = 1;
        while (v[b].empty()) ++b;
        last = v[b].back().first;
        for (int j = 0; j < int(v[b].size()); j++) last = std::min(last, v[b][j].first);
        for (int j = 0; j < int(v[b].size()); j++) {
            int i = v[b][j].second;
            auto bnxt = bucket(v[b][j].first ^ last);
            i2bj[i] = {bnxt, int(v[bnxt].size())}, v[bnxt].emplace_back(std::move(v[b][j]));
        }
        v[b].clear();
    }

public:
    radix_heap_array() : sz(0), last(0) {}
    bool empty() const noexcept { return sz == 0; }
    int argmin_pop() {
        pull(), --sz;
        int i = v[0].back().second;
        i2bj[i].j = -1;
        v[0].pop_back();
        return i;
    }
    void chmin(Uint vnew, int i) {
        if (i >= int(i2bj.size())) i2bj.resize(i + 1, {0, -1});
        if (i2bj[i].j < 0) {
            auto b = bucket(vnew ^ last);
            ++sz, i2bj[i] = {b, int(v[b].size())}, v[b].emplace_back(vnew, i);
        } else if (v[i2bj[i].b][i2bj[i].j].first > vnew) {
            auto bold = i2bj[i].b, bnew = bucket(vnew ^ last);
            if (bnew < bold) {
                int ilast = v[bold].back().second, j = i2bj[i].j;
                std::swap(v[bold][j], v[bold].back());
                i2bj[ilast].j = j, i2bj[i] = {bnew, int(v[bnew].size())};
                v[bnew].emplace_back(vnew, i), v[bold].pop_back();
            } else {
                v[bold][i2bj[i].j].first = vnew;
            }
        }
    }

    void pop() { argmin_pop(); }
    std::pair<Uint, int> top() { return pull(), v[0].back(); }
    [[deprecated("NOT usual emplace() opeation!")]] void emplace(Uint vnew, int i) { chmin(vnew, i); }

    void clear() noexcept { sz = 0, last = 0, i2bj.clear(); }
};

// CUT begin
// Minimum cost flow WITH NO NEGATIVE CYCLE (just negative cost edge is allowed)
// Verified:
// - SRM 770 Div1 Medium https://community.topcoder.com/stat?c=problem_statement&pm=15702
// - CodeChef LTIME98 Ancient Magic https://www.codechef.com/problems/ANCT
template <class Cap, class Cost, Cost INF_COST = std::numeric_limits<Cost>::max() / 2> struct MinCostFlow {
    template <class E> struct csr {
        std::vector<int> start;
        std::vector<E> elist;
        explicit csr(int n, const std::vector<std::pair<int, E>> &edges) : start(n + 1), elist(edges.size()) {
            for (auto e : edges) { start[e.first + 1]++; }
            for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; }
            auto counter = start;
            for (auto e : edges) { elist[counter[e.first]++] = e.second; }
        }
    };

public:
    MinCostFlow() {}
    explicit MinCostFlow(int n) : is_dual_infeasible(false), _n(n) {
        static_assert(std::numeric_limits<Cap>::max() > 0, "max() must be greater than 0");
    }

    int add_edge(int from, int to, Cap cap, Cost cost) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        // assert(0 <= cost);
        if (cost < 0) is_dual_infeasible = true;
        int m = int(_edges.size());
        _edges.push_back({from, to, cap, 0, cost});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
        Cost cost;
    };

    edge get_edge(int i) {
        int m = int(_edges.size());
        assert(0 <= i && i < m);
        return _edges[i];
    }
    std::vector<edge> edges() { return _edges; }

    std::pair<Cap, Cost> flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); }
    std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) { return slope(s, t, flow_limit).back(); }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
        return slope(s, t, std::numeric_limits<Cap>::max());
    }
    std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        int m = int(_edges.size());
        std::vector<int> edge_idx(m);

        auto g = [&]() {
            std::vector<int> degree(_n), redge_idx(m);
            std::vector<std::pair<int, _edge>> elist;
            elist.reserve(2 * m);
            for (int i = 0; i < m; i++) {
                auto e = _edges[i];
                edge_idx[i] = degree[e.from]++;
                redge_idx[i] = degree[e.to]++;
                elist.push_back({e.from, {e.to, -1, e.cap - e.flow, e.cost}});
                elist.push_back({e.to, {e.from, -1, e.flow, -e.cost}});
            }
            auto _g = csr<_edge>(_n, elist);
            for (int i = 0; i < m; i++) {
                auto e = _edges[i];
                edge_idx[i] += _g.start[e.from];
                redge_idx[i] += _g.start[e.to];
                _g.elist[edge_idx[i]].rev = redge_idx[i];
                _g.elist[redge_idx[i]].rev = edge_idx[i];
            }
            return _g;
        }();

        auto result = slope(g, s, t, flow_limit);

        for (int i = 0; i < m; i++) {
            auto e = g.elist[edge_idx[i]];
            _edges[i].flow = _edges[i].cap - e.cap;
        }

        return result;
    }

private:
    bool is_dual_infeasible;
    int _n;
    std::vector<edge> _edges;

    // inside edge
    struct _edge {
        int to, rev;
        Cap cap;
        Cost cost;
    };

    std::vector<std::pair<Cap, Cost>> slope(csr<_edge> &g, int s, int t, Cap flow_limit) {
        // variants (C = maxcost):
        // -(n-1)C <= dual[s] <= dual[i] <= dual[t] = 0
        // reduced cost (= e.cost + dual[e.from] - dual[e.to]) >= 0 for all edge

        // dual_dist[i] = (dual[i], dist[i])
        std::vector<std::pair<Cost, Cost>> dual_dist(_n);
        if (is_dual_infeasible) {
            auto check_dag = [&]() {
                std::vector<int> deg_in(_n);
                for (int v = 0; v < _n; v++) {
                    for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                        deg_in[g.elist[i].to] += g.elist[i].cap > 0;
                    }
                }
                std::vector<int> st;
                st.reserve(_n);
                for (int i = 0; i < _n; i++) {
                    if (!deg_in[i]) st.push_back(i);
                }
                for (int n = 0; n < _n; n++) {
                    if (int(st.size()) == n) return false; // Not DAG
                    int now = st[n];
                    for (int i = g.start[now]; i < g.start[now + 1]; i++) {
                        const auto &e = g.elist[i];
                        if (!e.cap) continue;
                        deg_in[e.to]--;
                        if (deg_in[e.to] == 0) st.push_back(e.to);
                        if (dual_dist[e.to].first >= dual_dist[now].first + e.cost)
                            dual_dist[e.to].first = dual_dist[now].first + e.cost;
                    }
                }
                return true;
            }();
            if (!check_dag) throw;
            auto dt = dual_dist[t].first;
            for (int v = 0; v < _n; v++) dual_dist[v].first -= dt;
            is_dual_infeasible = false;
        }
        std::vector<int> prev_e(_n);
        std::vector<bool> vis(_n);
        struct Q {
            Cost key;
            int to;
            bool operator<(Q r) const { return key > r.key; }
        };
        // std::vector<int> que_min;
        // std::vector<Q> que;
        auto dual_ref = [&]() {
            for (int i = 0; i < _n; i++) { dual_dist[i].second = std::numeric_limits<Cost>::max(); }
            std::fill(vis.begin(), vis.end(), false);
            // que_min.clear();
            // que.clear();

            // que[0..heap_r) was heapified
            // unsigned heap_r = 0;

            dual_dist[s].second = 0;
            // que_min.push_back(s);
            radix_heap_array<unsigned long long> heap;
            heap.chmin(0, s);
            // while (!que_min.empty() || !que.empty()) {
            while (!heap.empty()) {
                int v = heap.argmin_pop();
                // if (!que_min.empty()) {
                //     v = que_min.back();
                //     que_min.pop_back();
                // } else {
                //     while (heap_r < que.size()) {
                //         heap_r++;
                //         std::push_heap(que.begin(), que.begin() + heap_r);
                //     }
                //     v = que.front().to;
                //     std::pop_heap(que.begin(), que.end());
                //     que.pop_back();
                //     heap_r--;
                // }
                // if (vis[v]) continue;
                vis[v] = true;
                if (v == t) break;
                // dist[v] = shortest(s, v) + dual[s] - dual[v]
                // dist[v] >= 0 (all reduced cost are positive)
                // dist[v] <= (n-1)C
                Cost dual_v = dual_dist[v].first, dist_v = dual_dist[v].second;
                for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                    auto e = g.elist[i];
                    if (!e.cap) continue;
                    // |-dual[e.to] + dual[v]| <= (n-1)C
                    // cost <= C - -(n-1)C + 0 = nC
                    Cost cost = e.cost - dual_dist[e.to].first + dual_v;
                    if (dual_dist[e.to].second - dist_v > cost) {
                        Cost dist_to = dist_v + cost;
                        dual_dist[e.to].second = dist_to;
                        prev_e[e.to] = e.rev;
                        heap.chmin(dist_to, e.to);
                        // if (dist_to == dist_v) {
                        //     que_min.push_back(e.to);
                        // } else {
                        //     que.push_back(Q{dist_to, e.to});
                        // }
                    }
                }
            }
            if (!vis[t]) { return false; }

            for (int v = 0; v < _n; v++) {
                if (!vis[v]) continue;
                // dual[v] = dual[v] - dist[t] + dist[v]
                //         = dual[v] - (shortest(s, t) + dual[s] - dual[t]) +
                //         (shortest(s, v) + dual[s] - dual[v]) = - shortest(s,
                //         t) + dual[t] + shortest(s, v) = shortest(s, v) -
                //         shortest(s, t) >= 0 - (n-1)C
                dual_dist[v].first -= dual_dist[t].second - dual_dist[v].second;
            }
            return true;
        };
        Cap flow = 0;
        Cost cost = 0, prev_cost_per_flow = -1;
        std::vector<std::pair<Cap, Cost>> result = {{Cap(0), Cost(0)}};
        while (flow < flow_limit) {
            if (!dual_ref()) break;
            Cap c = flow_limit - flow;
            for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
                c = std::min(c, g.elist[g.elist[prev_e[v]].rev].cap);
            }
            for (int v = t; v != s; v = g.elist[prev_e[v]].to) {
                auto &e = g.elist[prev_e[v]];
                e.cap += c;
                g.elist[e.rev].cap -= c;
            }
            Cost d = -dual_dist[s].first;
            flow += c;
            cost += c * d;
            if (prev_cost_per_flow == d) { result.pop_back(); }
            result.push_back({flow, cost});
            prev_cost_per_flow = d;
        }
        return result;
    }
};
#line 3 "combinatorial_opt/test/mincostflow.yuki1288.test.cpp"
#include <iostream>
#include <numeric>
#include <string>
#line 7 "combinatorial_opt/test/mincostflow.yuki1288.test.cpp"
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    vector<long long> V(N);
    for (auto &x : V) cin >> x;

    const int s = N * 5, t = s + 1;
    MinCostFlow<int, long long> graph(t + 1);
    for (int d = 0; d < 5; d++) {
        for (int i = 0; i < N - 1; i++) graph.add_edge(d * N + i, d * N + i + 1, N / 4, 0);
    }
    graph.add_edge(s - 1, 0, N / 4, 0);

    for (int i = 0; i < N; i++) {
        int b = 0;
        if (S[i] == 'u') b = N * 1;
        if (S[i] == 'k') b = N * 2;
        if (S[i] == 'i') b = N * 3;
        int fr = b + i + N, to = b + i;
        graph.add_edge(s, fr, 1, 0);
        graph.add_edge(fr, to, 1, V[i]);
        graph.add_edge(to, t, 1, 0);
    }
    auto cost = graph.flow(s, t, N).second;
    cout << accumulate(V.begin(), V.end(), 0LL) - cost << '\n';
}
0