#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; } template bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; } const std::vector> grid_dxs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int floor_lg(long long x) { return x <= 0 ? -1 : 63 - __builtin_clzll(x); } template T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); } template std::pair operator+(const std::pair &l, const std::pair &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template std::pair operator-(const std::pair &l, const std::pair &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template std::vector sort_unique(std::vector vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; } template int arglb(const std::vector &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); } template int argub(const std::vector &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); } template IStream &operator>>(IStream &is, std::vector &vec) { for (auto &v : vec) is >> v; return is; } template OStream &operator<<(OStream &os, const std::vector &vec); template OStream &operator<<(OStream &os, const std::array &arr); template OStream &operator<<(OStream &os, const std::unordered_set &vec); template OStream &operator<<(OStream &os, const pair &pa); template OStream &operator<<(OStream &os, const std::deque &vec); template OStream &operator<<(OStream &os, const std::set &vec); template OStream &operator<<(OStream &os, const std::multiset &vec); template OStream &operator<<(OStream &os, const std::unordered_multiset &vec); template OStream &operator<<(OStream &os, const std::pair &pa); template OStream &operator<<(OStream &os, const std::map &mp); template OStream &operator<<(OStream &os, const std::unordered_map &mp); template OStream &operator<<(OStream &os, const std::tuple &tpl); template OStream &operator<<(OStream &os, const std::vector &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::array &arr) { os << '['; for (auto v : arr) os << v << ','; os << ']'; return os; } template std::istream &operator>>(std::istream &is, std::tuple &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);}, tpl); return is; } template OStream &operator<<(OStream &os, const std::tuple &tpl) { os << '('; std::apply([&os](auto &&... args) { ((os << args << ','), ...);}, tpl); return os << ')'; } template OStream &operator<<(OStream &os, const std::unordered_set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::deque &vec) { os << "deq["; for (auto v : vec) os << v << ','; os << ']'; return os; } template OStream &operator<<(OStream &os, const std::set &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_multiset &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::pair &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; } template OStream &operator<<(OStream &os, const std::map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } template OStream &operator<<(OStream &os, const std::unordered_map &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; } #ifdef HITONANODE_LOCAL const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m"; #define dbg(x) std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl #define dbgif(cond, x) ((cond) ? std::cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << std::endl : std::cerr) #else #define dbg(x) ((void)0) #define dbgif(cond, x) ((void)0) #endif #include #include #include #include namespace linear_sum_assignment { template struct Result { T opt; std::vector mate; std::vector f, g; // dual variables }; template T augment(int nr, int nc, const std::vector> &C, std::vector &f, std::vector &g, int s, // source row std::vector &mate, std::vector &mate_inv, // duplicates are allowed (used for k-best algorithms) int fixed_rows = 0 // Ignore first rows and corresponding columns (used for k-best algorithms) ) { assert(0 <= s and s < nr); assert(mate.at(s) < 0); static std::vector dist; static std::vector prv; dist.resize(nc); prv.resize(nc); std::vector done(nc); for (int i = 0; i < fixed_rows; ++i) { if (int j = mate.at(i); j >= 0) done.at(j) = 1; } { int h = 0; while (done.at(h)) ++h; f.at(s) = C.at(s).at(h) - g.at(h); for (int j = h + 1; j < nc; ++j) { if (done.at(j)) continue; f.at(s) = std::min(f.at(s), C.at(s).at(j) - g.at(j)); } } for (int j = 0; j < nc; ++j) { if (!done.at(j)) { dist.at(j) = C.at(s).at(j) - f.at(s) - g.at(j); prv.at(j) = -1; } } int t = -1; std::vector stk; while (t == -1) { int j1 = -1; for (int j = 0; j < nc; ++j) { if (done.at(j)) continue; if (j1 == -1 or dist.at(j) < dist.at(j1) or (dist.at(j) == dist.at(j1) and mate_inv.at(j) < 0)) { j1 = j; } } if (mate_inv.at(j1) < 0) { t = j1; break; } done.at(j1) = 1; stk = {j1}; while (!stk.empty()) { const int j2 = stk.back(); const int i = mate_inv.at(j2); if (i < 0) { t = stk.back(); break; } stk.pop_back(); for (int j = 0; j < nc; ++j) { if (done.at(j)) continue; const T len = C.at(i).at(j) - f.at(i) - g.at(j); if (dist.at(j) > dist.at(j1) + len) { dist.at(j) = dist.at(j1) + len; prv.at(j) = j2; } if (len == T()) { stk.push_back(j); done.at(j) = 1; } } } } const T len = dist.at(t); f.at(s) += len; for (int i = 0; i < fixed_rows; ++i) { if (const int j = mate.at(i); j >= 0) done.at(j) = 0; } for (int j = 0; j < nc; ++j) { if (!done.at(j)) continue; g.at(j) -= len - dist.at(j); } for (int i = fixed_rows; i < nr; ++i) { const int j = mate.at(i); if (j < 0 or !done.at(j) or j >= nc) continue; f.at(i) += len - dist.at(j); } T ret = T(); for (int cur = t; cur >= 0;) { const int nxt = prv.at(cur); if (nxt < 0) { mate_inv.at(cur) = s; mate.at(s) = cur; ret += C.at(s).at(cur); break; } const int i = mate_inv.at(nxt); ret += C.at(i).at(cur) - C.at(i).at(nxt); mate_inv.at(cur) = i; mate.at(i) = cur; cur = nxt; } return ret; } // Complexity: O(nr^2 nc) template Result _solve(int nr, int nc, const std::vector> &C) { assert(nr <= nc); std::vector mate(nr, -1); std::vector mate_inv(nc, -1); std::vector f(nr), g(nc); // dual variables, f[i] + g[j] <= C[i][j] holds if (nr == 0 or nc == 0) return {T(), mate, f, g}; if (nr == nc) { // Column reduction for (int j = nc - 1; j >= 0; --j) { g.at(j) = C.at(0).at(j) - f.at(0); int imin = 0; for (int i = 1; i < nr; ++i) { if (g.at(j) > C.at(i).at(j) - f.at(i)) { imin = i; g.at(j) = C.at(i).at(j) - f.at(i); } } if (mate.at(imin) < 0) { mate.at(imin) = j; mate_inv.at(j) = imin; } else if (g.at(j) < g.at(mate.at(imin))) { mate_inv.at(mate.at(imin)) = -1; mate.at(imin) = j; mate_inv.at(j) = imin; } } // Reduction transfer (can be omitted) if (nc > 1) { for (int i = 0; i < nr; ++i) { if (mate.at(i) < 0) continue; T best = C.at(i).at(0) - g.at(0), second_best = C.at(i).at(1) - g.at(1); int argbest = 0; if (best > second_best) std::swap(best, second_best), argbest = 1; for (int j = 2; j < nc; ++j) { if (T val = C.at(i).at(j) - g.at(j); val < best) { second_best = best; best = val; argbest = j; } else if (val < second_best) { second_best = val; } } g.at(argbest) -= second_best - best; f.at(i) = second_best; } } // Augmenting row reduction: not implemented } // Augmentation for (int i = 0; i < nr; ++i) { if (mate.at(i) < 0) augment(nr, nc, C, f, g, i, mate, mate_inv); } T ret = 0; for (int i = 0; i < nr; ++i) ret += C.at(i).at(mate.at(i)); return {ret, mate, std::move(f), std::move(g)}; } // Jonker–Volgenant algorithm: find minimum weight assignment // Dual problem (nr == nc): maximize sum(f) + sum(g) s.t. f_i + g_j <= C_ij // Complexity: O(nr nc min(nr, nc)) template Result solve(int nr, int nc, const std::vector> &C) { const bool transpose = (nr > nc); if (!transpose) return _solve(nr, nc, C); std::vector trans(nc, std::vector(nr)); for (int i = 0; i < nr; ++i) { for (int j = 0; j < nc; ++j) trans.at(j).at(i) = C.at(i).at(j); } auto [v, mate, f, g] = _solve(nc, nr, trans); std::vector mate2(nr, -1); for (int j = 0; j < nc; ++j) { if (mate.at(j) >= 0) mate2.at(mate.at(j)) = j; } return {v, mate2, g, f}; } } // namespace linear_sum_assignment template struct best_assignments { struct Node { T opt; std::vector mate; std::vector f, g; // dual variables int fixed_rows; std::vector banned_js; // C[fixed_rows][j] が inf となる j の集合 // for priority queue // NOTE: reverse order bool operator<(const Node &rhs) const { return opt > rhs.opt; } linear_sum_assignment::Result to_output(bool transpose) const { if (transpose) { std::vector mate2(g.size(), -1); for (int i = 0; i < (int)mate.size(); ++i) mate2.at(mate.at(i)) = i; return {opt, mate2, g, f}; } else { return {opt, mate, f, g}; } } }; bool transpose; int nr_, nc_; T inf; std::vector> C_, Ctmp_; std::priority_queue pq; best_assignments(int nr, int nc, const std::vector> &C, T inf) : transpose(nr > nc), inf(inf) { assert((int)C.size() == nr); for (int i = 0; i < nr; ++i) assert((int)C.at(i).size() == nc); nr_ = transpose ? nc : nr; nc_ = transpose ? nr : nc; C_.assign(nr_ + (nr_ != nc_), std::vector(nc_, T())); for (int i = 0; i < nr; ++i) { for (int j = 0; j < nc; ++j) { C_.at(transpose ? j : i).at(transpose ? i : j) = C.at(i).at(j); } } Ctmp_ = C_; auto [opt, mate, f, g] = linear_sum_assignment::solve(C_.size(), nc, C_); pq.emplace(Node{opt, std::move(mate), std::move(f), std::move(g), 0, {}}); } bool finished() const { return pq.empty(); } linear_sum_assignment::Result yield() { assert(!pq.empty()); const Node ret = pq.top(); pq.pop(); for (int fixed_rows = ret.fixed_rows; fixed_rows < nr_; ++fixed_rows) { std::vector banned_js; if (fixed_rows == ret.fixed_rows) banned_js = ret.banned_js; const int s = fixed_rows; banned_js.push_back(ret.mate.at(s)); if ((int)banned_js.size() >= nc_) continue; auto f = ret.f; auto g = ret.g; auto mate = ret.mate; std::vector mate_inv(nc_, nr_); for (int i = 0; i < nr_; ++i) mate_inv.at(mate.at(i)) = i; std::vector iscoldone(nc_); for (int i = 0; i < fixed_rows; ++i) iscoldone.at(mate.at(i)) = 1; for (int j : banned_js) Ctmp_.at(s).at(j) = inf; mate_inv.at(mate.at(s)) = -1; mate.at(s) = -1; auto aug = linear_sum_assignment::augment( nr_, nc_, Ctmp_, f, g, s, mate, mate_inv, fixed_rows); for (int j = 0; j < nc_; ++j) { if (mate_inv.at(j) < 0) { // nrows < ncols g.at(j) = -f.back(); for (int i = fixed_rows; i < nr_; ++i) { g.at(j) = std::min(g.at(j), Ctmp_.at(i).at(j) - f.at(i)); } } } if (Ctmp_.at(s).at(mate.at(s)) < inf) { pq.emplace(Node{ ret.opt + aug - C_.at(s).at(ret.mate.at(s)), std::move(mate), std::move(f), std::move(g), fixed_rows, banned_js, }); } for (int j : banned_js) Ctmp_.at(s).at(j) = C_.at(s).at(j); } return ret.to_output(transpose); } }; int main() { int N, M; cin >> N >> M; vector A(N, vector(M)); cin >> A; const int K = N / 2; vector mat(K, vector(K)); REP(i, K) REP(j, K) { int best = 0; REP(k, M) chmax(best, A.at(N - 1 - j).at(k) - A.at(i).at(k)); mat.at(i).at(j) = -best; } auto res = linear_sum_assignment::solve(K, K, mat); cout << -res.opt << '\n'; }