QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#174840 | #7185. Poor Students | ucup-team1951 | AC ✓ | 1089ms | 83424kb | C++17 | 49.7kb | 2023-09-10 13:50:52 | 2023-09-10 13:50:52 |
Judging History
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