QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174840#7185. Poor Studentsucup-team1951AC ✓1089ms83424kbC++1749.7kb2023-09-10 13:50:522023-09-10 13:50:52

Judging History

你现在查看的是最新测评结果

  • [2023-09-10 13:50:52]
  • 评测
  • 测评结果:AC
  • 用时:1089ms
  • 内存:83424kb
  • [2023-09-10 13:50:52]
  • 提交

answer

// g++-13 1.cpp -std=c++17 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;
 
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

// CUT begin
// This program is the modificatiosn of the [lemon::NetworkSimplex](http://lemon.cs.elte.hu/pub/doc/latest-svn/a00404.html)
//
/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2013
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */


template <class Digraph, typename V = int, typename C = V> class NetworkSimplex {
public:
    using Node = int;
    using Arc = int;
    static const int INVALID = -1;
    typedef V Value; /// The type of the flow amounts, capacity bounds and supply values
    typedef C Cost;  /// The type of the arc costs

public:
    enum ProblemType { INFEASIBLE, OPTIMAL, UNBOUNDED };

    /// \brief Constants for selecting the type of the supply constraints.
    ///
    /// Enum type containing constants for selecting the supply type,
    /// i.e. the direction of the inequalities in the supply/demand
    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
    ///
    /// The default supply type is \c GEQ, the \c LEQ type can be
    /// selected using \ref supplyType().
    /// The equality form is a special case of both supply types.
    enum SupplyType {
        /// This option means that there are <em>"greater or equal"</em>
        /// supply/demand constraints in the definition of the problem.
        GEQ,
        /// This option means that there are <em>"less or equal"</em>
        /// supply/demand constraints in the definition of the problem.
        LEQ
    };

    /// \brief Constants for selecting the pivot rule.
    ///
    /// Enum type containing constants for selecting the pivot rule for
    /// the \ref run() function.
    ///
    /// \ref NetworkSimplex provides five different implementations for
    /// the pivot strategy that significantly affects the running time
    /// of the algorithm.
    /// According to experimental tests conducted on various problem
    /// instances, \ref BLOCK_SEARCH "Block Search" and
    /// \ref ALTERING_LIST "Altering Candidate List" rules turned out
    /// to be the most efficient.
    /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that
    /// seemed to be slightly more robust, it is used by default.
    /// However, another pivot rule can easily be selected using the
    /// \ref run() function with the proper parameter.
    enum PivotRule {

        /// The \e First \e Eligible pivot rule.
        /// The next eligible arc is selected in a wraparound fashion
        /// in every iteration.
        FIRST_ELIGIBLE,

        /// The \e Best \e Eligible pivot rule.
        /// The best eligible arc is selected in every iteration.
        BEST_ELIGIBLE,

        /// The \e Block \e Search pivot rule.
        /// A specified number of arcs are examined in every iteration
        /// in a wraparound fashion and the best eligible arc is selected
        /// from this block.
        BLOCK_SEARCH,

        /// The \e Candidate \e List pivot rule.
        /// In a major iteration a candidate list is built from eligible arcs
        /// in a wraparound fashion and in the following minor iterations
        /// the best eligible arc is selected from this list.
        CANDIDATE_LIST,

        /// The \e Altering \e Candidate \e List pivot rule.
        /// It is a modified version of the Candidate List method.
        /// It keeps only a few of the best eligible arcs from the former
        /// candidate list and extends this list in every iteration.
        ALTERING_LIST
    };

private:
    using IntVector = std::vector<int>;
    using ValueVector = std::vector<Value>;
    using CostVector = std::vector<Cost>;
    using CharVector = std::vector<signed char>;
    enum ArcState { STATE_UPPER = -1, STATE_TREE = 0, STATE_LOWER = 1 };
    enum ArcDirection { DIR_DOWN = -1, DIR_UP = 1 };

private:
    // Data related to the underlying digraph
    const Digraph &_graph;
    int _node_num;
    int _arc_num;
    int _all_arc_num;
    int _search_arc_num;

    // Parameters of the problem
    bool _has_lower;
    SupplyType _stype;
    Value _sum_supply;

    // Data structures for storing the digraph
    IntVector _source;
    IntVector _target;

    // Node and arc data
    ValueVector _lower;
    ValueVector _upper;
    ValueVector _cap;
    CostVector _cost;
    ValueVector _supply;
    ValueVector _flow;
    CostVector _pi;

    // Data for storing the spanning tree structure
    IntVector _parent;
    IntVector _pred;
    IntVector _thread;
    IntVector _rev_thread;
    IntVector _succ_num;
    IntVector _last_succ;
    CharVector _pred_dir;
    CharVector _state;
    IntVector _dirty_revs;
    int _root;

    // Temporary data used in the current pivot iteration
    int in_arc, join, u_in, v_in, u_out, v_out;
    Value delta;

    const Value MAX;

public:
    /// \brief Constant for infinite upper bounds (capacities).
    ///
    /// Constant for infinite upper bounds (capacities).
    /// It is \c std::numeric_limits<Value>::infinity() if available,
    /// \c std::numeric_limits<Value>::max() otherwise.
    const Value INF;

private:
    // Implementation of the First Eligible pivot rule
    class FirstEligiblePivotRule {
    private:
        // References to the NetworkSimplex class
        const IntVector &_source;
        const IntVector &_target;
        const CostVector &_cost;
        const CharVector &_state;
        const CostVector &_pi;
        int &_in_arc;
        int _search_arc_num;

        // Pivot rule data
        int _next_arc;

    public:
        // Constructor
        FirstEligiblePivotRule(NetworkSimplex &ns)
            : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), _next_arc(0) {}

        // Find next entering arc
        bool findEnteringArc() {
            Cost c;
            for (int e = _next_arc; e != _search_arc_num; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _in_arc = e;
                    _next_arc = e + 1;
                    return true;
                }
            }
            for (int e = 0; e != _next_arc; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _in_arc = e;
                    _next_arc = e + 1;
                    return true;
                }
            }
            return false;
        }

    }; // class FirstEligiblePivotRule

    // Implementation of the Best Eligible pivot rule
    class BestEligiblePivotRule {
    private:
        // References to the NetworkSimplex class
        const IntVector &_source;
        const IntVector &_target;
        const CostVector &_cost;
        const CharVector &_state;
        const CostVector &_pi;
        int &_in_arc;
        int _search_arc_num;

    public:
        // Constructor
        BestEligiblePivotRule(NetworkSimplex &ns)
            : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num) {}

        // Find next entering arc
        bool findEnteringArc() {
            Cost c, min = 0;
            for (int e = 0; e != _search_arc_num; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < min) {
                    min = c;
                    _in_arc = e;
                }
            }
            return min < 0;
        }

    }; // class BestEligiblePivotRule

    // Implementation of the Block Search pivot rule
    class BlockSearchPivotRule {
    private:
        // References to the NetworkSimplex class
        const IntVector &_source;
        const IntVector &_target;
        const CostVector &_cost;
        const CharVector &_state;
        const CostVector &_pi;
        int &_in_arc;
        int _search_arc_num;

        // Pivot rule data
        int _block_size;
        int _next_arc;

    public:
        // Constructor
        BlockSearchPivotRule(NetworkSimplex &ns)
            : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), _next_arc(0) {
            // The main parameters of the pivot rule
            const double BLOCK_SIZE_FACTOR = 1.0;
            const int MIN_BLOCK_SIZE = 10;

            _block_size = std::max(int(BLOCK_SIZE_FACTOR * std::sqrt(double(_search_arc_num))), MIN_BLOCK_SIZE);
        }

        // Find next entering arc
        bool findEnteringArc() {
            Cost c, min = 0;
            int cnt = _block_size;
            int e;
            for (e = _next_arc; e != _search_arc_num; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < min) {
                    min = c;
                    _in_arc = e;
                }
                if (--cnt == 0) {
                    if (min < 0) goto search_end;
                    cnt = _block_size;
                }
            }
            for (e = 0; e != _next_arc; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < min) {
                    min = c;
                    _in_arc = e;
                }
                if (--cnt == 0) {
                    if (min < 0) goto search_end;
                    cnt = _block_size;
                }
            }
            if (min >= 0) return false;

        search_end:
            _next_arc = e;
            return true;
        }

    }; // class BlockSearchPivotRule

    // Implementation of the Candidate List pivot rule
    class CandidateListPivotRule {
    private:
        // References to the NetworkSimplex class
        const IntVector &_source;
        const IntVector &_target;
        const CostVector &_cost;
        const CharVector &_state;
        const CostVector &_pi;
        int &_in_arc;
        int _search_arc_num;

        // Pivot rule data
        IntVector _candidates;
        int _list_length, _minor_limit;
        int _curr_length, _minor_count;
        int _next_arc;

    public:
        /// Constructor
        CandidateListPivotRule(NetworkSimplex &ns)
            : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), _next_arc(0) {
            // The main parameters of the pivot rule
            const double LIST_LENGTH_FACTOR = 0.25;
            const int MIN_LIST_LENGTH = 10;
            const double MINOR_LIMIT_FACTOR = 0.1;
            const int MIN_MINOR_LIMIT = 3;

            _list_length = std::max(int(LIST_LENGTH_FACTOR * std::sqrt(double(_search_arc_num))), MIN_LIST_LENGTH);
            _minor_limit = std::max(int(MINOR_LIMIT_FACTOR * _list_length), MIN_MINOR_LIMIT);
            _curr_length = _minor_count = 0;
            _candidates.resize(_list_length);
        }

        /// Find next entering arc
        bool findEnteringArc() {
            Cost min, c;
            int e;
            if (_curr_length > 0 && _minor_count < _minor_limit) {
                // Minor iteration: select the best eligible arc from the
                // current candidate list
                ++_minor_count;
                min = 0;
                for (int i = 0; i < _curr_length; ++i) {
                    e = _candidates[i];
                    c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                    if (c < min) {
                        min = c;
                        _in_arc = e;
                    } else if (c >= 0) {
                        _candidates[i--] = _candidates[--_curr_length];
                    }
                }
                if (min < 0) return true;
            }

            // Major iteration: build a new candidate list
            min = 0;
            _curr_length = 0;
            for (e = _next_arc; e != _search_arc_num; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _candidates[_curr_length++] = e;
                    if (c < min) {
                        min = c;
                        _in_arc = e;
                    }
                    if (_curr_length == _list_length) goto search_end;
                }
            }
            for (e = 0; e != _next_arc; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _candidates[_curr_length++] = e;
                    if (c < min) {
                        min = c;
                        _in_arc = e;
                    }
                    if (_curr_length == _list_length) goto search_end;
                }
            }
            if (_curr_length == 0) return false;

        search_end:
            _minor_count = 1;
            _next_arc = e;
            return true;
        }

    }; // class CandidateListPivotRule

    // Implementation of the Altering Candidate List pivot rule
    class AlteringListPivotRule {
    private:
        // References to the NetworkSimplex class
        const IntVector &_source;
        const IntVector &_target;
        const CostVector &_cost;
        const CharVector &_state;
        const CostVector &_pi;
        int &_in_arc;
        int _search_arc_num;

        // Pivot rule data
        int _block_size, _head_length, _curr_length;
        int _next_arc;
        IntVector _candidates;
        CostVector _cand_cost;

        // Functor class to compare arcs during sort of the candidate list
        class SortFunc {
        private:
            const CostVector &_map;

        public:
            SortFunc(const CostVector &map) : _map(map) {}
            bool operator()(int left, int right) { return _map[left] < _map[right]; }
        };

        SortFunc _sort_func;

    public:
        // Constructor
        AlteringListPivotRule(NetworkSimplex &ns)
            : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _search_arc_num(ns._search_arc_num), _next_arc(0), _cand_cost(ns._search_arc_num), _sort_func(_cand_cost) {
            // The main parameters of the pivot rule
            const double BLOCK_SIZE_FACTOR = 1.0;
            const int MIN_BLOCK_SIZE = 10;
            const double HEAD_LENGTH_FACTOR = 0.01;
            const int MIN_HEAD_LENGTH = 3;

            _block_size = std::max(int(BLOCK_SIZE_FACTOR * std::sqrt(double(_search_arc_num))), MIN_BLOCK_SIZE);
            _head_length = std::max(int(HEAD_LENGTH_FACTOR * _block_size), MIN_HEAD_LENGTH);
            _candidates.resize(_head_length + _block_size);
            _curr_length = 0;
        }

        // Find next entering arc
        bool findEnteringArc() {
            // Check the current candidate list
            int e;
            Cost c;
            for (int i = 0; i != _curr_length; ++i) {
                e = _candidates[i];
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _cand_cost[e] = c;
                } else {
                    _candidates[i--] = _candidates[--_curr_length];
                }
            }

            // Extend the list
            int cnt = _block_size;
            int limit = _head_length;

            for (e = _next_arc; e != _search_arc_num; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _cand_cost[e] = c;
                    _candidates[_curr_length++] = e;
                }
                if (--cnt == 0) {
                    if (_curr_length > limit) goto search_end;
                    limit = 0;
                    cnt = _block_size;
                }
            }
            for (e = 0; e != _next_arc; ++e) {
                c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]);
                if (c < 0) {
                    _cand_cost[e] = c;
                    _candidates[_curr_length++] = e;
                }
                if (--cnt == 0) {
                    if (_curr_length > limit) goto search_end;
                    limit = 0;
                    cnt = _block_size;
                }
            }
            if (_curr_length == 0) return false;

        search_end:

            // Perform partial sort operation on the candidate list
            int new_length = std::min(_head_length + 1, _curr_length);
            std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, _candidates.begin() + _curr_length, _sort_func);

            // Select the entering arc and remove it from the list
            _in_arc = _candidates[0];
            _next_arc = e;
            _candidates[0] = _candidates[new_length - 1];
            _curr_length = new_length - 1;
            return true;
        }

    }; // class AlteringListPivotRule

public:
    NetworkSimplex(const Digraph &graph)
        : _graph(graph), MAX(std::numeric_limits<Value>::max()), INF(std::numeric_limits<Value>::has_infinity ? std::numeric_limits<Value>::infinity() : MAX) {
        // Check the number types
        static_assert(std::numeric_limits<Value>::is_signed, "Value must be signed");
        static_assert(std::numeric_limits<Cost>::is_signed, "Cost must be signed");
        static_assert(std::numeric_limits<Value>::max() > 0, "max() must be greater than 0");

        // Reset data structures
        reset();
    }

    template <typename LowerMap> NetworkSimplex &lowerMap(const LowerMap &map) {
        _has_lower = true;
        for (Arc a = 0; a < _arc_num; a++) _lower[a] = map[a];
        return *this;
    }
    template <typename UpperMap> NetworkSimplex &upperMap(const UpperMap &map) {
        for (Arc a = 0; a < _arc_num; a++) _upper[a] = map[a];
        return *this;
    }
    // Set costs of arcs (default value: 1)
    template <typename CostMap> NetworkSimplex &costMap(const CostMap &map) {
        for (Arc a = 0; a < _arc_num; a++) _cost[a] = map[a];
        return *this;
    }
    template <typename SupplyMap> NetworkSimplex &supplyMap(const SupplyMap &map) {
        for (Node n = 0; n < _node_num; n++) _supply[n] = map[n];
        return *this;
    }
    NetworkSimplex &stSupply(const Node &s, const Node &t, Value k) { // set s-t flow
        for (int i = 0; i != _node_num; ++i) _supply[i] = 0;
        _supply[s] = k, _supply[t] = -k;
        return *this;
    }

    /// \brief Set the type of the supply constraints.
    ///
    /// This function sets the type of the supply/demand constraints.
    /// If it is not used before calling \ref run(), the \ref GEQ supply
    /// type will be used.
    NetworkSimplex &supplyType(SupplyType supply_type) {
        _stype = supply_type;
        return *this;
    }

    /// @}

    /// This function can be called more than once. All the given parameters
    /// are kept for the next call, unless \ref resetParams() or \ref reset()
    /// is used, thus only the modified parameters have to be set again.
    /// If the underlying digraph was also modified after the construction
    /// of the class (or the last \ref reset() call), then the \ref reset()
    /// function must be called.
    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
        if (!init()) return INFEASIBLE;
        return start(pivot_rule);
    }

    /// \brief Reset all the parameters that have been given before.
    ///
    /// This function resets all the paramaters that have been given
    /// before using functions \ref lowerMap(), \ref upperMap(),
    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    ///
    /// It is useful for multiple \ref run() calls. Basically, all the given
    /// parameters are kept for the next \ref run() call, unless
    /// \ref resetParams() or \ref reset() is used.
    /// If the underlying digraph was also modified after the construction
    /// of the class or the last \ref reset() call, then the \ref reset()
    /// function must be used, otherwise \ref resetParams() is sufficient.
    ///
    /// For example,
    /// \code
    ///   NetworkSimplex<ListDigraph> ns(graph);
    ///
    ///   // First run
    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
    ///     .supplyMap(sup).run();
    ///
    ///   // Run again with modified cost map (resetParams() is not called,
    ///   // so only the cost map have to be set again)
    ///   cost[e] += 100;
    ///   ns.costMap(cost).run();
    ///
    ///   // Run again from scratch using resetParams()
    ///   // (the lower bounds will be set to zero on all arcs)
    ///   ns.resetParams();
    ///   ns.upperMap(capacity).costMap(cost)
    ///     .supplyMap(sup).run();
    /// \endcode
    ///
    /// \return <tt>(*this)</tt>
    ///
    /// \see reset(), run()
    NetworkSimplex &resetParams() {
        for (int i = 0; i != _node_num; ++i) { _supply[i] = 0; }
        for (int i = 0; i != _arc_num; ++i) {
            _lower[i] = 0;
            _upper[i] = INF;
            _cost[i] = 1;
        }
        _has_lower = false;
        _stype = GEQ;
        return *this;
    }

    /// \brief Reset the internal data structures and all the parameters
    /// that have been given before.
    ///
    /// This function resets the internal data structures and all the
    /// paramaters that have been given before using functions \ref lowerMap(),
    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
    /// \ref supplyType().
    ///
    /// It is useful for multiple \ref run() calls. Basically, all the given
    /// parameters are kept for the next \ref run() call, unless
    /// \ref resetParams() or \ref reset() is used.
    /// If the underlying digraph was also modified after the construction
    /// of the class or the last \ref reset() call, then the \ref reset()
    /// function must be used, otherwise \ref resetParams() is sufficient.
    ///
    /// See \ref resetParams() for examples.
    ///
    /// \return <tt>(*this)</tt>
    ///
    /// \see resetParams(), run()
    NetworkSimplex &reset() {
        // Resize vectors
        _node_num = _graph.countNodes();
        _arc_num = _graph.countArcs();
        int all_node_num = _node_num + 1;
        int max_arc_num = _arc_num + 2 * _node_num;

        _source.resize(max_arc_num);
        _target.resize(max_arc_num);

        _lower.resize(_arc_num);
        _upper.resize(_arc_num);
        _cap.resize(max_arc_num);
        _cost.resize(max_arc_num);
        _supply.resize(all_node_num);
        _flow.resize(max_arc_num);
        _pi.resize(all_node_num);

        _parent.resize(all_node_num);
        _pred.resize(all_node_num);
        _pred_dir.resize(all_node_num);
        _thread.resize(all_node_num);
        _rev_thread.resize(all_node_num);
        _succ_num.resize(all_node_num);
        _last_succ.resize(all_node_num);
        _state.resize(max_arc_num);

        for (int a = 0; a < _arc_num; ++a) {
            _source[a] = _graph.source(a);
            _target[a] = _graph.target(a);
        }
        // Reset parameters
        resetParams();
        return *this;
    }

    /// @}

    template <typename Number = Cost> Number totalCost() const {
        Number c = 0;
        for (Arc a = 0; a < _arc_num; a++) c += Number(_flow[a]) * Number(_cost[a]);
        return c;
    }

    Value flow(const Arc &a) const { return _flow[a]; }
    template <typename FlowMap> void flowMap(FlowMap &map) const {
        for (Arc a = 0; a < _arc_num; a++) { map.set(a, _flow[a]); }
    }
    ValueVector flowMap() const { return _flow; }

    Cost potential(const Node &n) const { return _pi[n]; }
    template <typename PotentialMap> void potentialMap(PotentialMap &map) const {
        for (int n = 0; n < _graph.V; n++) { map.set(n, _pi[n]); }
    }
    CostVector potentialMap() const { return _pi; }

private:
    // Initialize internal data structures
    bool init() {
        if (_node_num == 0) return false;

        // Check the sum of supply values
        _sum_supply = 0;
        for (int i = 0; i != _node_num; ++i) { _sum_supply += _supply[i]; }
        if (!((_stype == GEQ && _sum_supply <= 0) || (_stype == LEQ && _sum_supply >= 0))) return false;

        // Check lower and upper bounds
        // LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds");

        // Remove non-zero lower bounds
        if (_has_lower) {
            for (int i = 0; i != _arc_num; ++i) {
                Value c = _lower[i];
                if (c >= 0) {
                    _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
                } else {
                    _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
                }
                _supply[_source[i]] -= c;
                _supply[_target[i]] += c;
            }
        } else {
            for (int i = 0; i != _arc_num; ++i) { _cap[i] = _upper[i]; }
        }

        // Initialize artifical cost
        Cost ART_COST;
        if (std::numeric_limits<Cost>::is_exact) {
            ART_COST = std::numeric_limits<Cost>::max() / 2 + 1;
        } else {
            ART_COST = 0;
            for (int i = 0; i != _arc_num; ++i) {
                if (_cost[i] > ART_COST) ART_COST = _cost[i];
            }
            ART_COST = (ART_COST + 1) * _node_num;
        }

        // Initialize arc maps
        for (int i = 0; i != _arc_num; ++i) {
            _flow[i] = 0;
            _state[i] = STATE_LOWER;
        }

        // Set data for the artificial root node
        _root = _node_num;
        _parent[_root] = -1;
        _pred[_root] = -1;
        _thread[_root] = 0;
        _rev_thread[0] = _root;
        _succ_num[_root] = _node_num + 1;
        _last_succ[_root] = _root - 1;
        _supply[_root] = -_sum_supply;
        _pi[_root] = 0;

        // Add artificial arcs and initialize the spanning tree data structure
        if (_sum_supply == 0) {
            // EQ supply constraints
            _search_arc_num = _arc_num;
            _all_arc_num = _arc_num + _node_num;
            for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
                _parent[u] = _root;
                _pred[u] = e;
                _thread[u] = u + 1;
                _rev_thread[u + 1] = u;
                _succ_num[u] = 1;
                _last_succ[u] = u;
                _cap[e] = INF;
                _state[e] = STATE_TREE;
                if (_supply[u] >= 0) {
                    _pred_dir[u] = DIR_UP;
                    _pi[u] = 0;
                    _source[e] = u;
                    _target[e] = _root;
                    _flow[e] = _supply[u];
                    _cost[e] = 0;
                } else {
                    _pred_dir[u] = DIR_DOWN;
                    _pi[u] = ART_COST;
                    _source[e] = _root;
                    _target[e] = u;
                    _flow[e] = -_supply[u];
                    _cost[e] = ART_COST;
                }
            }
        } else if (_sum_supply > 0) {
            // LEQ supply constraints
            _search_arc_num = _arc_num + _node_num;
            int f = _arc_num + _node_num;
            for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
                _parent[u] = _root;
                _thread[u] = u + 1;
                _rev_thread[u + 1] = u;
                _succ_num[u] = 1;
                _last_succ[u] = u;
                if (_supply[u] >= 0) {
                    _pred_dir[u] = DIR_UP;
                    _pi[u] = 0;
                    _pred[u] = e;
                    _source[e] = u;
                    _target[e] = _root;
                    _cap[e] = INF;
                    _flow[e] = _supply[u];
                    _cost[e] = 0;
                    _state[e] = STATE_TREE;
                } else {
                    _pred_dir[u] = DIR_DOWN;
                    _pi[u] = ART_COST;
                    _pred[u] = f;
                    _source[f] = _root;
                    _target[f] = u;
                    _cap[f] = INF;
                    _flow[f] = -_supply[u];
                    _cost[f] = ART_COST;
                    _state[f] = STATE_TREE;
                    _source[e] = u;
                    _target[e] = _root;
                    _cap[e] = INF;
                    _flow[e] = 0;
                    _cost[e] = 0;
                    _state[e] = STATE_LOWER;
                    ++f;
                }
            }
            _all_arc_num = f;
        } else {
            // GEQ supply constraints
            _search_arc_num = _arc_num + _node_num;
            int f = _arc_num + _node_num;
            for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
                _parent[u] = _root;
                _thread[u] = u + 1;
                _rev_thread[u + 1] = u;
                _succ_num[u] = 1;
                _last_succ[u] = u;
                if (_supply[u] <= 0) {
                    _pred_dir[u] = DIR_DOWN;
                    _pi[u] = 0;
                    _pred[u] = e;
                    _source[e] = _root;
                    _target[e] = u;
                    _cap[e] = INF;
                    _flow[e] = -_supply[u];
                    _cost[e] = 0;
                    _state[e] = STATE_TREE;
                } else {
                    _pred_dir[u] = DIR_UP;
                    _pi[u] = -ART_COST;
                    _pred[u] = f;
                    _source[f] = u;
                    _target[f] = _root;
                    _cap[f] = INF;
                    _flow[f] = _supply[u];
                    _state[f] = STATE_TREE;
                    _cost[f] = ART_COST;
                    _source[e] = _root;
                    _target[e] = u;
                    _cap[e] = INF;
                    _flow[e] = 0;
                    _cost[e] = 0;
                    _state[e] = STATE_LOWER;
                    ++f;
                }
            }
            _all_arc_num = f;
        }

        return true;
    }

    // Check if the upper bound is greater than or equal to the lower bound
    // on each arc.
    bool checkBoundMaps() {
        for (int j = 0; j != _arc_num; ++j) {
            if (_upper[j] < _lower[j]) return false;
        }
        return true;
    }

    // Find the join node
    void findJoinNode() {
        int u = _source[in_arc];
        int v = _target[in_arc];
        while (u != v) {
            if (_succ_num[u] < _succ_num[v]) {
                u = _parent[u];
            } else {
                v = _parent[v];
            }
        }
        join = u;
    }

    // Find the leaving arc of the cycle and returns true if the
    // leaving arc is not the same as the entering arc
    bool findLeavingArc() {
        // Initialize first and second nodes according to the direction
        // of the cycle
        int first, second;
        if (_state[in_arc] == STATE_LOWER) {
            first = _source[in_arc];
            second = _target[in_arc];
        } else {
            first = _target[in_arc];
            second = _source[in_arc];
        }
        delta = _cap[in_arc];
        int result = 0;
        Value c, d;
        int e;

        // Search the cycle form the first node to the join node
        for (int u = first; u != join; u = _parent[u]) {
            e = _pred[u];
            d = _flow[e];
            if (_pred_dir[u] == DIR_DOWN) {
                c = _cap[e];
                d = c >= MAX ? INF : c - d;
            }
            if (d < delta) {
                delta = d;
                u_out = u;
                result = 1;
            }
        }

        // Search the cycle form the second node to the join node
        for (int u = second; u != join; u = _parent[u]) {
            e = _pred[u];
            d = _flow[e];
            if (_pred_dir[u] == DIR_UP) {
                c = _cap[e];
                d = c >= MAX ? INF : c - d;
            }
            if (d <= delta) {
                delta = d;
                u_out = u;
                result = 2;
            }
        }

        if (result == 1) {
            u_in = first;
            v_in = second;
        } else {
            u_in = second;
            v_in = first;
        }
        return result != 0;
    }

    // Change _flow and _state vectors
    void changeFlow(bool change) {
        // Augment along the cycle
        if (delta > 0) {
            Value val = _state[in_arc] * delta;
            _flow[in_arc] += val;
            for (int u = _source[in_arc]; u != join; u = _parent[u]) {
                _flow[_pred[u]] -= _pred_dir[u] * val;
            }
            for (int u = _target[in_arc]; u != join; u = _parent[u]) {
                _flow[_pred[u]] += _pred_dir[u] * val;
            }
        }
        // Update the state of the entering and leaving arcs
        if (change) {
            _state[in_arc] = STATE_TREE;
            _state[_pred[u_out]] = (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
        } else {
            _state[in_arc] = -_state[in_arc];
        }
    }

    // Update the tree structure
    void updateTreeStructure() {
        int old_rev_thread = _rev_thread[u_out];
        int old_succ_num = _succ_num[u_out];
        int old_last_succ = _last_succ[u_out];
        v_out = _parent[u_out];

        // Check if u_in and u_out coincide
        if (u_in == u_out) {
            // Update _parent, _pred, _pred_dir
            _parent[u_in] = v_in;
            _pred[u_in] = in_arc;
            _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;

            // Update _thread and _rev_thread
            if (_thread[v_in] != u_out) {
                int after = _thread[old_last_succ];
                _thread[old_rev_thread] = after;
                _rev_thread[after] = old_rev_thread;
                after = _thread[v_in];
                _thread[v_in] = u_out;
                _rev_thread[u_out] = v_in;
                _thread[old_last_succ] = after;
                _rev_thread[after] = old_last_succ;
            }
        } else {
            // Handle the case when old_rev_thread equals to v_in
            // (it also means that join and v_out coincide)
            int thread_continue = old_rev_thread == v_in ? _thread[old_last_succ] : _thread[v_in];

            // Update _thread and _parent along the stem nodes (i.e. the nodes
            // between u_in and u_out, whose parent have to be changed)
            int stem = u_in;             // the current stem node
            int par_stem = v_in;         // the new parent of stem
            int next_stem;               // the next stem node
            int last = _last_succ[u_in]; // the last successor of stem
            int before, after = _thread[last];
            _thread[v_in] = u_in;
            _dirty_revs.clear();
            _dirty_revs.push_back(v_in);
            while (stem != u_out) {
                // Insert the next stem node into the thread list
                next_stem = _parent[stem];
                _thread[last] = next_stem;
                _dirty_revs.push_back(last);

                // Remove the subtree of stem from the thread list
                before = _rev_thread[stem];
                _thread[before] = after;
                _rev_thread[after] = before;

                // Change the parent node and shift stem nodes
                _parent[stem] = par_stem;
                par_stem = stem;
                stem = next_stem;

                // Update last and after
                last = _last_succ[stem] == _last_succ[par_stem] ? _rev_thread[par_stem] : _last_succ[stem];
                after = _thread[last];
            }
            _parent[u_out] = par_stem;
            _thread[last] = thread_continue;
            _rev_thread[thread_continue] = last;
            _last_succ[u_out] = last;

            // Remove the subtree of u_out from the thread list except for
            // the case when old_rev_thread equals to v_in
            if (old_rev_thread != v_in) {
                _thread[old_rev_thread] = after;
                _rev_thread[after] = old_rev_thread;
            }

            // Update _rev_thread using the new _thread values
            for (int i = 0; i != int(_dirty_revs.size()); ++i) {
                int u = _dirty_revs[i];
                _rev_thread[_thread[u]] = u;
            }

            // Update _pred, _pred_dir, _last_succ and _succ_num for the
            // stem nodes from u_out to u_in
            int tmp_sc = 0, tmp_ls = _last_succ[u_out];
            for (int u = u_out, p = _parent[u]; u != u_in; u = p, p = _parent[u]) {
                _pred[u] = _pred[p];
                _pred_dir[u] = -_pred_dir[p];
                tmp_sc += _succ_num[u] - _succ_num[p];
                _succ_num[u] = tmp_sc;
                _last_succ[p] = tmp_ls;
            }
            _pred[u_in] = in_arc;
            _pred_dir[u_in] = u_in == _source[in_arc] ? DIR_UP : DIR_DOWN;
            _succ_num[u_in] = old_succ_num;
        }

        // Update _last_succ from v_in towards the root
        int up_limit_out = _last_succ[join] == v_in ? join : -1;
        int last_succ_out = _last_succ[u_out];
        for (int u = v_in; u != -1 && _last_succ[u] == v_in; u = _parent[u]) {
            _last_succ[u] = last_succ_out;
        }

        // Update _last_succ from v_out towards the root
        if (join != old_rev_thread && v_in != old_rev_thread) {
            for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; u = _parent[u]) {
                _last_succ[u] = old_rev_thread;
            }
        } else if (last_succ_out != old_last_succ) {
            for (int u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; u = _parent[u]) {
                _last_succ[u] = last_succ_out;
            }
        }

        // Update _succ_num from v_in to join
        for (int u = v_in; u != join; u = _parent[u]) { _succ_num[u] += old_succ_num; }
        // Update _succ_num from v_out to join
        for (int u = v_out; u != join; u = _parent[u]) { _succ_num[u] -= old_succ_num; }
    }

    // Update potentials in the subtree that has been moved
    void updatePotential() {
        Cost sigma = _pi[v_in] - _pi[u_in] - _pred_dir[u_in] * _cost[in_arc];
        int end = _thread[_last_succ[u_in]];
        for (int u = u_in; u != end; u = _thread[u]) { _pi[u] += sigma; }
    }

    // Heuristic initial pivots
    bool initialPivots() {
        Value curr, total = 0;
        std::vector<Node> supply_nodes, demand_nodes;
        for (int u = 0; u < _node_num; ++u) {
            curr = _supply[u];
            if (curr > 0) {
                total += curr;
                supply_nodes.push_back(u);
            } else if (curr < 0) {
                demand_nodes.push_back(u);
            }
        }
        if (_sum_supply > 0) total -= _sum_supply;
        if (total <= 0) return true;

        IntVector arc_vector;
        if (_sum_supply >= 0) {
            if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {
                // Perform a reverse graph search from the sink to the source
                std::vector<char> reached(_node_num, false);
                Node s = supply_nodes[0], t = demand_nodes[0];
                std::vector<Node> stack;
                reached[t] = true;
                stack.push_back(t);
                while (!stack.empty()) {
                    Node u, v = stack.back();
                    stack.pop_back();
                    if (v == s) break;
                    // for (InArcIt a(_graph, v); a != INVALID; ++a) {
                    for (auto a : _graph.in_eids[v]) {
                        if (reached[u = _graph.source(a)]) continue;
                        int j = a;
                        if (_cap[j] >= total) {
                            arc_vector.push_back(j);
                            reached[u] = true;
                            stack.push_back(u);
                        }
                    }
                }
            } else {
                // Find the min. cost incoming arc for each demand node
                for (int i = 0; i != int(demand_nodes.size()); ++i) {
                    Node v = demand_nodes[i];
                    Cost c, min_cost = std::numeric_limits<Cost>::max();
                    Arc min_arc = INVALID;
                    for (auto a : _graph.in_eids[v]) {
                        // for (InArcIt a(_graph, v); a != INVALID; ++a) {
                        c = _cost[a];
                        if (c < min_cost) {
                            min_cost = c;
                            min_arc = a;
                        }
                    }
                    if (min_arc != INVALID) { arc_vector.push_back(min_arc); }
                }
            }
        } else {
            // Find the min. cost outgoing arc for each supply node
            for (Node u : supply_nodes) {
                Cost c, min_cost = std::numeric_limits<Cost>::max();
                Arc min_arc = INVALID;
                for (auto a : _graph.out_eids[u]) {
                    c = _cost[a];
                    if (c < min_cost) {
                        min_cost = c;
                        min_arc = a;
                    }
                }
                if (min_arc != INVALID) { arc_vector.push_back(min_arc); }
            }
        }

        // Perform heuristic initial pivots
        for (int i = 0; i != int(arc_vector.size()); ++i) {
            in_arc = arc_vector[i];
            if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] - _pi[_target[in_arc]]) >= 0) continue;
            findJoinNode();
            bool change = findLeavingArc();
            if (delta >= MAX) return false;
            changeFlow(change);
            if (change) {
                updateTreeStructure();
                updatePotential();
            }
        }
        return true;
    }

    // Execute the algorithm
    ProblemType start(PivotRule pivot_rule) {
        // Select the pivot rule implementation
        switch (pivot_rule) {
        case FIRST_ELIGIBLE: return start<FirstEligiblePivotRule>();
        case BEST_ELIGIBLE: return start<BestEligiblePivotRule>();
        case BLOCK_SEARCH: return start<BlockSearchPivotRule>();
        case CANDIDATE_LIST: return start<CandidateListPivotRule>();
        case ALTERING_LIST: return start<AlteringListPivotRule>();
        }
        return INFEASIBLE; // avoid warning
    }

    template <typename PivotRuleImpl> ProblemType start() {
        PivotRuleImpl pivot(*this);

        // Perform heuristic initial pivots
        if (!initialPivots()) return UNBOUNDED;

        // Execute the Network Simplex algorithm
        while (pivot.findEnteringArc()) {
            findJoinNode();
            bool change = findLeavingArc();
            if (delta >= MAX) return UNBOUNDED;
            changeFlow(change);
            if (change) {
                updateTreeStructure();
                updatePotential();
            }
        }

        // Check feasibility
        for (int e = _search_arc_num; e != _all_arc_num; ++e) {
            if (_flow[e] != 0) return INFEASIBLE;
        }

        // Transform the solution and the supply map to the original form
        if (_has_lower) {
            for (int i = 0; i != _arc_num; ++i) {
                Value c = _lower[i];
                if (c != 0) {
                    _flow[i] += c;
                    _supply[_source[i]] += c;
                    _supply[_target[i]] -= c;
                }
            }
        }

        // Shift potentials to meet the requirements of the GEQ/LEQ type
        // optimality conditions
        if (_sum_supply == 0) {
            if (_stype == GEQ) {
                Cost max_pot = -std::numeric_limits<Cost>::max();
                for (int i = 0; i != _node_num; ++i) {
                    if (_pi[i] > max_pot) max_pot = _pi[i];
                }
                if (max_pot > 0) {
                    for (int i = 0; i != _node_num; ++i) _pi[i] -= max_pot;
                }
            } else {
                Cost min_pot = std::numeric_limits<Cost>::max();
                for (int i = 0; i != _node_num; ++i) {
                    if (_pi[i] < min_pot) min_pot = _pi[i];
                }
                if (min_pot < 0) {
                    for (int i = 0; i != _node_num; ++i) _pi[i] -= min_pot;
                }
            }
        }

        return OPTIMAL;
    }
}; // class NetworkSimplex

template <typename Capacity = long long, typename Weight = long long> struct mcf_graph_ns {

    struct Digraph {
        const int V;
        int E;
        std::vector<std::vector<int>> in_eids, out_eids;
        std::vector<std::pair<int, int>> arcs;
        Digraph(int V = 0) : V(V), E(0), in_eids(V), out_eids(V){};
        int add_edge(int s, int t) {
            assert(0 <= s and s < V);
            assert(0 <= t and t < V);
            in_eids[t].push_back(E), out_eids[s].push_back(E), arcs.emplace_back(s, t), E++;
            return E - 1;
        }
        int countNodes() const noexcept { return V; }
        int countArcs() const noexcept { return E; }
        int source(int arcid) const { return arcs[arcid].first; }
        int target(int arcid) const { return arcs[arcid].second; }
    };

    struct edge {
        int eid;
        int from, to;
        Capacity lo, hi;
        Weight weight;
    };

    int n;
    std::vector<Capacity> bs;
    bool infeasible;
    std::vector<edge> Edges;

    mcf_graph_ns(int V = 0) : n(V), bs(V), infeasible(false) {}

    int add_edge(int from, int to, Capacity lower, Capacity upper, Weight weight) {
        assert(from >= 0 and from < n);
        assert(to >= 0 and to < n);
        int idnow = Edges.size();
        Edges.push_back({idnow, from, to, lower, upper, weight});
        return idnow;
    }
    void set_supply(int v, Capacity b) {
        assert(v >= 0 and v < n);
        bs[v] = b;
    }
    std::vector<Capacity> flow;
    std::vector<Capacity> potential;

    template <typename RetVal = __int128> [[nodiscard]] RetVal solve() {
        std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

        std::vector<int> vid(n), eid(Edges.size());
        std::iota(vid.begin(), vid.end(), 0);
        std::shuffle(vid.begin(), vid.end(), rng);
        std::iota(eid.begin(), eid.end(), 0);
        std::shuffle(eid.begin(), eid.end(), rng);

        flow.clear();
        potential.clear();
        Digraph graph(n + 1);

        std::vector<Capacity> supplies(graph.countNodes());
        std::vector<Capacity> lowers(Edges.size());
        std::vector<Capacity> uppers(Edges.size());
        std::vector<Weight> weights(Edges.size());

        for (int i = 0; i < n; i++) supplies[vid[i]] = bs[i];
        for (auto i : eid) {
            const auto &e = Edges[i];
            int arc = graph.add_edge(vid[e.from], vid[e.to]);
            lowers[arc] = e.lo;
            uppers[arc] = e.hi;
            weights[arc] = e.weight;
        }

        NetworkSimplex<Digraph, Capacity, Weight> ns(graph);
        auto status = ns.supplyMap(supplies).costMap(weights).lowerMap(lowers).upperMap(uppers).run(decltype(ns)::BLOCK_SEARCH);

        if (status == decltype(ns)::INFEASIBLE) {
            return infeasible = true, 0;
        } else {
            flow.resize(Edges.size());
            potential.resize(n);
            for (int i = 0; i < int(Edges.size()); i++) flow[eid[i]] = ns.flow(i);
            for (int i = 0; i < n; i++) potential[i] = ns.potential(vid[i]);
            return ns.template totalCost<RetVal>();
        }
    }
};

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n,k;cin>>n>>k;
  vvll c(n,vll(k));
  vi a(k);
  rep(i,0,n)rep(j,0,k)cin>>c[i][j];
  rep(i,0,k)cin>>a[i];

  mcf_graph_ns<int,ll> graph(n+k+2);

  rep(i,0,n){
    graph.add_edge(n+k,i,0,1,0);
  }
  rep(i,0,k){
    graph.add_edge(n+i,n+k+1,0,a[i],0);
  }
  rep(i,0,n){
    rep(j,0,k){
      graph.add_edge(i,n+j,0,1,c[i][j]);
    }
  }

  graph.set_supply(n+k,n);
  graph.set_supply(n+k+1,-n);

  ll ans=graph.solve();
  cout<<ans<<endl;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3492kb

input:

6 2
1 2
1 3
1 4
1 5
1 6
1 7
3 4

output:

12

result:

ok answer is '12'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

3 3
1 2 3
2 4 6
6 5 4
1 1 1

output:

8

result:

ok answer is '8'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4668kb

input:

1000 10
734 303 991 681 755 155 300 483 702 442
237 256 299 675 671 757 112 853 759 233
979 340 288 377 718 199 935 666 576 842
537 363 592 349 494 961 864 727 84 813
340 78 600 492 118 421 478 925 552 617
517 589 716 7 928 638 258 297 706 787
266 746 913 978 436 859 701 951 137 44
815 336 471 720 2...

output:

92039

result:

ok answer is '92039'

Test #4:

score: 0
Accepted
time: 22ms
memory: 10932kb

input:

5000 10
14 114 254 832 38 904 25 147 998 785
917 694 750 372 379 887 247 817 999 117
802 15 799 515 316 42 69 247 95 144
727 398 509 725 682 456 369 656 693 955
923 1 681 631 962 826 233 963 289 856
165 491 488 832 111 950 853 791 929 240
509 843 667 970 469 260 447 477 161 431
514 903 627 236 144 3...

output:

461878

result:

ok answer is '461878'

Test #5:

score: 0
Accepted
time: 58ms
memory: 18152kb

input:

10000 10
307 205 765 487 504 526 10 581 234 583
448 443 39 992 976 363 335 588 588 169
920 787 896 822 47 358 230 631 136 299
141 159 414 852 922 945 513 76 111 189
616 104 83 792 24 68 164 975 615 472
150 108 848 517 7 153 107 283 452 165
94 370 910 662 226 720 975 214 324 407
636 65 963 859 590 3 ...

output:

919745

result:

ok answer is '919745'

Test #6:

score: 0
Accepted
time: 638ms
memory: 80100kb

input:

50000 10
819 49 278 985 747 872 146 129 898 569
929 427 54 846 136 475 448 304 591 428
238 844 664 991 990 863 308 571 867 958
775 690 792 697 557 325 824 654 303 833
542 942 262 534 501 575 273 60 701 488
733 855 810 405 294 909 638 975 801 836
382 265 818 765 240 69 980 889 472 211
629 434 128 389...

output:

4558242

result:

ok answer is '4558242'

Test #7:

score: 0
Accepted
time: 733ms
memory: 78576kb

input:

50000 10
381 642 238 598 634 432 828 277 275 239
963 771 114 457 411 717 85 260 527 664
138 832 923 332 197 371 30 412 47 568
266 38 327 563 564 14 943 698 881 747
627 788 567 438 371 524 490 674 809 839
322 680 178 515 376 355 928 880 827 446
702 107 650 811 360 226 283 138 357 489
121 364 656 377 ...

output:

4595976

result:

ok answer is '4595976'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

5 3
2 4 5
5 9 9
2 7 9
4 2 2
4 1 7
3 3 3

output:

12

result:

ok answer is '12'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

10 7
1 9 9 3 5 5 7
6 1 6 3 4 3 6
9 6 8 5 5 2 7
3 8 8 6 6 6 3
5 8 1 9 7 9 5
3 2 3 7 7 8 7
4 1 2 3 3 3 7
8 1 7 3 4 2 7
7 1 1 9 2 7 3
4 9 8 9 6 8 9
10 2 1 1 2 1 1

output:

21

result:

ok answer is '21'

Test #10:

score: 0
Accepted
time: 29ms
memory: 14908kb

input:

10000 7
6 5 9 8 5 5 5
2 4 5 2 7 8 9
7 3 7 2 6 8 8
8 1 6 4 8 6 9
2 3 8 1 3 5 5
1 5 6 1 3 1 6
2 7 7 3 5 9 5
1 9 9 6 8 5 5
1 4 2 4 6 7 7
8 4 1 5 2 2 1
7 9 9 5 5 1 2
9 7 1 3 9 5 9
6 7 3 6 3 8 3
7 7 2 4 2 4 5
5 5 9 8 2 4 9
9 5 8 4 7 2 9
4 3 4 8 4 3 3
8 3 7 9 6 6 6
5 4 5 2 6 3 9
4 9 5 6 1 3 2
4 1 2 6 6 5 ...

output:

44137

result:

ok answer is '44137'

Test #11:

score: 0
Accepted
time: 64ms
memory: 13648kb

input:

10000 6
3 4 1 4 5 4
4 4 3 7 7 2
6 6 8 1 9 9
2 5 5 1 7 3
9 7 7 3 3 8
5 7 1 2 6 3
2 8 9 4 9 1
4 8 3 2 1 7
4 9 2 3 8 5
1 6 2 2 9 1
1 4 9 8 9 6
3 8 3 7 6 1
3 1 5 7 9 5
5 3 8 1 2 8
5 1 8 3 9 4
1 5 4 5 5 4
9 4 1 8 8 4
5 6 7 5 8 2
3 1 6 2 3 1
2 7 4 8 5 6
5 4 3 2 5 1
8 5 4 7 3 2
7 5 2 3 1 1
3 1 1 7 3 1
2 6 ...

output:

21143

result:

ok answer is '21143'

Test #12:

score: 0
Accepted
time: 72ms
memory: 13908kb

input:

10000 6
26621560 22574851 99124663 42644108 73831692 34062679
10875678 33632518 99379217 52587402 68258572 82863
6133022 1452838 27530175 15603746 10928055 64045100
4919237 15636901 89763 37033224 76358345 23420261
87262364 92257115 7193645 40262131 78897499 70538741
45451167 2937593 39330094 300263...

output:

176215561116

result:

ok answer is '176215561116'

Test #13:

score: 0
Accepted
time: 66ms
memory: 13464kb

input:

10000 6
505488678 436228096 333558553 129070925 123808864 36937787
503324046 79831519 80269630 548781256 374673233 280839716
209008459 554326459 255308141 256669834 530478297 51026940
351489261 459988802 392737197 83890293 359338753 331620684
201060883 194683095 375867041 232603637 138654087 1929412...

output:

1034670171939

result:

ok answer is '1034670171939'

Test #14:

score: 0
Accepted
time: 69ms
memory: 13488kb

input:

10000 6
89916134 29433813 59399087 464898320 558107935 422188143
547054926 559929858 728302681 5219270 834478116 259909510
816488311 368359373 194676880 330286055 245200722 87979527
63366579 585173909 706460949 49644677 770070184 329255152
314412303 288716719 333799370 614570900 406350296 696208263
...

output:

1773428571657

result:

ok answer is '1773428571657'

Test #15:

score: 0
Accepted
time: 30ms
memory: 14356kb

input:

10000 6
66237379 181806248 509510118 323698055 917981861 381020346
891370175 602465447 651904218 27588579 475265754 430666261
874613865 991962519 265069683 393546179 987679666 717041057
675429255 645133077 623980032 953549198 946201757 765785432
954715369 623518217 681467056 740740198 415802185 5827...

output:

1439875611641

result:

ok answer is '1439875611641'

Test #16:

score: 0
Accepted
time: 52ms
memory: 13424kb

input:

10000 6
109501946 925691998 114115135 829446594 173795627 891153669
264844500 481537403 422647594 964796147 386517450 581623444
921172582 375091327 237314301 608361127 357677517 595119843
119651751 659029470 938251974 210093064 369958476 821941442
411555569 328723790 979811779 137795697 512892726 39...

output:

1561994475072

result:

ok answer is '1561994475072'

Test #17:

score: 0
Accepted
time: 32ms
memory: 14832kb

input:

10000 6
214242852 862344228 444719752 969065314 468060368 232241544
786803413 801480781 666280058 298466884 28589081 984412665
436101075 178002287 220595950 936235752 308790537 65171840
853973125 4091452 854764838 888615836 554917488 238207448
499378894 673682464 358195819 455995859 52657992 5920135...

output:

1444521827648

result:

ok answer is '1444521827648'

Test #18:

score: 0
Accepted
time: 116ms
memory: 32272kb

input:

50000 2
3 8
8 3
4 9
4 7
6 6
9 1
5 6
2 1
8 6
4 1
2 5
2 7
8 4
1 9
2 6
6 5
9 8
2 2
8 8
4 1
3 2
5 8
9 7
5 4
8 6
9 4
3 8
7 3
4 3
6 4
1 1
5 5
1 6
2 8
8 1
3 2
7 6
3 7
5 2
6 3
6 2
1 2
1 4
3 2
8 1
9 4
4 8
6 9
5 7
4 2
5 1
1 7
4 9
9 9
4 3
4 1
9 9
1 4
7 5
7 2
5 1
3 2
7 7
6 7
7 9
1 2
9 1
5 2
7 6
9 9
3 4
9 6
8 4
...

output:

176124

result:

ok answer is '176124'

Test #19:

score: 0
Accepted
time: 654ms
memory: 32488kb

input:

50000 2
7 8
7 2
1 7
4 7
9 3
9 5
6 7
9 5
6 5
5 9
2 8
7 2
1 1
3 6
5 1
6 1
3 4
4 3
7 4
5 7
8 6
4 2
7 7
7 6
3 1
2 6
5 5
4 7
2 2
6 7
4 7
7 7
6 5
5 1
7 6
7 1
4 9
3 4
8 9
1 2
4 5
6 7
5 1
6 9
7 8
7 3
3 2
2 6
6 5
1 1
7 5
6 5
8 4
6 1
9 2
6 3
2 8
9 2
9 2
4 1
6 5
8 7
3 4
2 2
9 5
4 4
8 9
8 1
9 5
5 7
6 7
8 6
8 8
...

output:

177533

result:

ok answer is '177533'

Test #20:

score: 0
Accepted
time: 1089ms
memory: 79588kb

input:

50000 10
1824 2363 5240 1212 3128 7792 4378 6737 6873 4561
6684 2808 5841 7269 1104 3757 7 9932 9632 4854
9932 4447 2965 3922 7850 6872 2608 9167 1883 5406
4782 7230 3002 8699 1262 2250 7887 4108 3047 4316
7201 9791 1853 6276 3058 7801 9499 1955 1574 772
5864 9874 1922 7714 9288 7860 1638 1972 1656 ...

output:

97744364

result:

ok answer is '97744364'

Test #21:

score: 0
Accepted
time: 308ms
memory: 78140kb

input:

50000 10
2805 3778 5335 84 1469 5531 8230 3676 9657 9550
7655 7925 1349 2743 9386 5272 5208 2769 222 8429
1441 5456 9320 5457 2254 6681 9525 6966 7646 2514
1106 2451 4523 1117 1452 5136 940 8349 4325 2506
7565 6257 6307 7785 1758 3084 7702 7174 6598 7917
2295 5399 2630 7826 5276 2830 7127 3433 630 1...

output:

47609008

result:

ok answer is '47609008'

Test #22:

score: 0
Accepted
time: 366ms
memory: 78984kb

input:

50000 10
4945 8281 7207 7498 3135 8902 3753 327 6931 5403
6843 5658 677 1566 9115 1116 364 8522 779 3707
6088 9697 79 2726 2110 9645 989 8787 2103 2703
3400 1962 340 3137 893 9996 5450 5835 7875 8223
5758 1518 630 3244 9952 1634 3541 4997 9420 1849
6417 1897 6413 5377 4786 8664 9382 5744 712 7626
12...

output:

48029932

result:

ok answer is '48029932'

Test #23:

score: 0
Accepted
time: 341ms
memory: 80500kb

input:

50000 10
8529 6814 3851 4143 3281 5256 2152 4151 6603 1490
596 5776 2024 2601 8258 5037 9756 7162 3910 5345
2901 3606 8604 7462 4615 8766 7644 1766 6005 7156
3448 3495 8566 5637 6960 584 5808 8731 2487 1587
3713 6662 6804 3305 5368 6442 5711 9987 3312 5151
7534 6034 257 6354 242 153 1360 484 1661 40...

output:

47775092

result:

ok answer is '47775092'

Test #24:

score: 0
Accepted
time: 317ms
memory: 79672kb

input:

50000 10
9682 8540 9492 7313 2454 4895 3643 1211 8946 1585
7855 4409 2505 5409 2345 7514 6159 1886 9560 3269
4954 5885 4932 4971 2250 9970 196 6165 619 7168
3846 486 5876 1308 3852 3602 7292 8837 565 1949
9568 5610 3776 613 6981 1203 9620 8008 1297 985
5454 1611 1535 8118 2584 5499 5665 8593 9884 15...

output:

47895396

result:

ok answer is '47895396'

Test #25:

score: 0
Accepted
time: 265ms
memory: 80272kb

input:

50000 10
6315 1094 894 7236 9575 6742 8643 2222 5263 5134
8928 5850 2780 8036 5217 3974 3627 6242 2413 7632
9825 7173 796 4751 3519 7903 8846 7614 3191 226
3610 1474 6537 5242 6730 4646 607 6436 3100 7641
8242 2270 5848 2927 5187 2638 479 5104 6901 4498
4149 805 858 7173 1808 6254 8207 8165 3086 195...

output:

45828764

result:

ok answer is '45828764'

Test #26:

score: 0
Accepted
time: 271ms
memory: 80244kb

input:

50000 10
1229 2898 2885 4865 6967 4324 500 9786 2817 6978
8202 9199 5946 5254 3333 3481 2890 3283 3986 4275
3786 4058 2787 352 8245 7036 652 2541 1064 9755
1663 4816 6843 5152 4725 8980 9082 4721 4774 1961
5037 71 7875 9461 7575 3314 9465 1973 1343 9534
5794 1349 8338 2855 2041 2396 8642 546 8932 83...

output:

45736329

result:

ok answer is '45736329'

Test #27:

score: 0
Accepted
time: 421ms
memory: 79184kb

input:

50000 10
4991 9685 5723 8310 5162 7991 464 6415 1322 3335
9344 1092 9504 618 8107 3351 3112 5980 8207 5642
2055 8198 7808 6384 5241 3049 8681 4319 1536 6342
8037 9510 1057 9213 1670 2006 5192 9950 1286 3550
433 5598 4689 7502 8528 8901 175 8348 5080 8090
6633 2978 3979 2622 625 1146 3089 9429 5453 3...

output:

53803793

result:

ok answer is '53803793'

Test #28:

score: 0
Accepted
time: 370ms
memory: 83424kb

input:

50000 10
263 656 3591 2040 5059 2270 7622 5964 6749 5948
4162 70 158 9650 2122 6575 1502 5657 6210 6038
4713 1055 5829 529 9034 104 634 1607 3206 7265
4994 2527 7411 478 3170 6469 7429 7058 771 3917
7281 2429 4624 4186 6297 3407 2238 296 265 5263
2117 1809 6514 1616 9666 6464 2410 1384 1373 8286
545...

output:

50558646

result:

ok answer is '50558646'

Test #29:

score: 0
Accepted
time: 733ms
memory: 78392kb

input:

50000 10
680 2925 5108 5577 2822 1996 3730 9647 7399 8687
7313 3213 9023 5630 2334 7289 9086 9325 8365 9689
1309 4675 9888 9178 3206 142 7170 5693 5800 9625
2605 2567 9968 4546 2536 1068 1321 6574 3020 8794
7616 7586 2993 8538 439 5218 6931 7176 2081 9802
6890 9158 7006 1873 2829 4993 7479 5303 6862...

output:

45229804

result:

ok answer is '45229804'

Test #30:

score: 0
Accepted
time: 632ms
memory: 80640kb

input:

50000 10
3074 2857 3294 4431 4370 8319 547 4845 5048 4999
3655 8903 1933 7601 7526 8563 8970 3670 7905 8003
8826 8566 8148 6835 3515 6643 7 6476 5572 4712
801 576 2340 7154 3373 9212 3757 9020 1176 9520
4267 6001 5775 423 932 5956 1473 5602 5438 4260
6 7166 1406 8728 3695 3187 971 7430 7331 7781
614...

output:

45312529

result:

ok answer is '45312529'

Test #31:

score: 0
Accepted
time: 795ms
memory: 78380kb

input:

50000 10
5467 2789 3062 3284 7499 3060 7363 1625 4278 1310
8415 4593 3259 7990 2720 8255 8855 8014 7445 6317
4762 2457 4827 4492 3825 4726 4426 7260 6925 8215
8996 8583 6292 9762 5791 8938 6192 3049 7750 248
9335 2834 8557 2307 9842 6694 4432 4029 8795 301
3122 6756 5804 4003 4562 9799 6044 1141 621...

output:

45456618

result:

ok answer is '45456618'

Test #32:

score: 0
Accepted
time: 788ms
memory: 79456kb

input:

50000 10
3852 3910 6453 6900 6508 5019 2082 1809 6259 9731
8387 6909 7753 5836 5327 4534 6798 5644 9002 6443
8907 153 9181 5627 7240 4337 621 2629 1961 9766
9792 1028 9843 8015 4311 1823 9318 8173 6917 9831
6535 1197 1850 6857 8688 7270 5455 223 4911 4826
1342 7306 1554 551 4254 5557 1712 8649 9136 ...

output:

45328645

result:

ok answer is '45328645'

Test #33:

score: 0
Accepted
time: 597ms
memory: 79308kb

input:

50000 10
5911 2041 3972 1678 6278 7712 1178 9746 7745 1624
8966 8591 2535 5523 9403 1674 4538 3309 9919 4964
8532 1170 2446 3593 6191 8405 939 2779 1292 5186
8432 5638 73 6188 9419 2281 3325 4049 7761 471
9741 555 7129 2388 4992 914 7428 6035 6267 4270
9476 3518 1536 4698 6632 8290 7804 7861 7552 34...

output:

45457443

result:

ok answer is '45457443'

Test #34:

score: 0
Accepted
time: 393ms
memory: 80344kb

input:

50000 10
76551321 42771251 50102295 39280938 45263454 79797046 10803054 45781565 77089368 91227654
80058111 7361931 74490827 87574706 49601805 87737654 35832951 29590101 53663591 33462640
22171056 57518634 47955581 40395087 31331896 51706118 50229887 68108693 6779469 18400895
1709708 82136753 887660...

output:

456114887126

result:

ok answer is '456114887126'

Test #35:

score: 0
Accepted
time: 754ms
memory: 80428kb

input:

50000 10
4330 9027 7145 71 8528 5890 6082 3462 8563 4617
5545 7238 6009 1677 1088 8637 6692 1329 3301 2856
4674 1804 7507 8905 8467 5816 6435 4954 8302 6939
5757 6212 1875 1766 2949 3425 6435 6804 4675 8362
4466 7436 2338 9021 9964 5122 407 5420 4006 8034
2933 3010 4403 4310 7602 840 9559 3975 6295 ...

output:

76544399

result:

ok answer is '76544399'

Test #36:

score: 0
Accepted
time: 922ms
memory: 79520kb

input:

50000 10
776 2211 5484 5959 5115 4627 4304 5723 9672 7936
689 5523 6730 8572 3675 7448 383 9202 8749 7960
2346 9927 6316 2650 5126 1942 5545 4333 6438 3919
7126 3597 4706 2010 9687 2492 4237 9944 5663 4051
2519 7049 3649 1168 5704 3605 4082 2049 3821 4965
4325 9463 2492 1457 8464 6164 7917 6512 8262...

output:

76249432

result:

ok answer is '76249432'

Extra Test:

score: 0
Extra Test Passed