結果
| 問題 | No.2573 moving up |
| ユーザー |
 hitonanode
|
| 提出日時 | 2023-12-02 15:46:37 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 12,734 bytes |
| コンパイル時間 | 2,645 ms |
| コンパイル使用メモリ | 202,020 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-27 01:27:17 |
| 合計ジャッジ時間 | 3,352 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 31 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <deque>#include <forward_list>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iostream>#include <limits>#include <list>#include <map>#include <memory>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <tuple>#include <type_traits>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;using lint = long long;using pint = pair<int, int>;using plint = pair<lint, lint>;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##_end_;i++)#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }const std::vector<std::pair<int, int>> 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 <class T1, class T2> T1 floor_div(T1 num, T2 den) { return (num > 0 ? num / den : -((-num + den - 1) / den)); }template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }template <class T> int arglb(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::lower_bound(v.begin(), v.end(), x)); }template <class T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec);template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr);template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa);template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec);template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec);template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa);template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp);template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp);template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl);template <class OStream, class T> OStream &operator<<(OStream &os, const std::vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const std::array<T, sz> &arr) { os << '['; for (auto v : arr) os << v<< ','; os << ']'; return os; }template <class... T> std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) { std::apply([&is](auto &&... args) { ((is >> args), ...);},tpl); return is; }template <class OStream, class... T> OStream &operator<<(OStream &os, const std::tuple<T...> &tpl) { os << '('; std::apply([&os](auto &&... args) {((os << args << ','), ...);}, tpl); return os << ')'; }template <class OStream, class T, class TH> OStream &operator<<(OStream &os, const std::unordered_set<T, TH> &vec) { os << '{'; for (auto v : vec) os<< v << ','; os << '}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ','; os <<']'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::set<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os << '}';return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::multiset<T> &vec) { os << '{'; for (auto v : vec) os << v << ','; os <<'}'; return os; }template <class OStream, class T> OStream &operator<<(OStream &os, const std::unordered_multiset<T> &vec) { os << '{'; for (auto v : vec) os << v <<','; os << '}'; return os; }template <class OStream, class T, class U> OStream &operator<<(OStream &os, const std::pair<T, U> &pa) { return os << '(' << pa.first << ',' << pa.second << ')'; }template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const std::map<TK, TV> &mp) { os << '{'; for (auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }template <class OStream, class TK, class TV, class TH> OStream &operator<<(OStream &os, const std::unordered_map<TK, TV, TH> &mp) { os << '{'; for(auto v : mp) os << v.first << "=>" << v.second << ','; os << '}'; return os; }#ifdef HITONANODE_LOCALconst 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 <cassert>#include <tuple>#include <vector>namespace linear_sum_assignment {template <class T>T augment(int nr, int nc, const std::vector<std::vector<T>> &C, std::vector<T> &f,std::vector<T> &g, int s, std::vector<int> &mate, std::vector<int> &mate_inv) {assert(0 <= s and s < nr);assert(mate.at(s) < 0);static std::vector<T> dist;static std::vector<int> prv;dist.resize(nc);prv.resize(nc);f.at(s) = C.at(s).at(0) - g.at(0);for (int j = 1; j < nc; ++j) f.at(s) = std::min(f.at(s), C.at(s).at(j) - g.at(j));for (int j = 0; j < nc; ++j) {dist.at(j) = C.at(s).at(j) - f.at(s) - g.at(j);prv.at(j) = s;}std::vector<bool> done(nc);int t = -1;std::vector<int> 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 (j1 == -1) return false;if (mate_inv.at(j1) < 0) {t = j1;break;}done.at(j1) = 1;stk = {j1};while (!stk.empty()) {const int i = mate_inv.at(stk.back());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) = i;}if (len == T()) {stk.push_back(j);done.at(j) = 1;}}}}const T len = dist.at(t);f.at(s) += len;T ret = len;for (int j = 0; j < nc; ++j) {if (!done.at(j)) continue;g.at(j) -= len - dist.at(j);if (mate_inv.at(j) >= 0) {f.at(mate_inv.at(j)) += len - dist.at(j);} else {ret -= len - dist.at(j);}}for (int cur = t; cur >= 0;) {const int i = prv.at(cur);mate_inv.at(cur) = i;if (i == -1) break;std::swap(cur, mate.at(i));}return ret;}// Complexity: O(nr^2 nc)template <class T>std::tuple<T, std::vector<int>, std::vector<T>, std::vector<T>>_solve(int nr, int nc, const std::vector<std::vector<T>> &C) {assert(nr <= nc);std::vector<int> mate(nr, -1);std::vector<int> mate_inv(nc, -1);std::vector<T> f(nr), g(nc); // dual variables, f[i] + g[j] <= C[i][j] holdsif (nr == 0 or nc == 0) return {T(), mate, f, g};if (nr == nc) {// Column reductionfor (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}// Augmentationfor (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 <class T>std::tuple<T, std::vector<int>, std::vector<T>, std::vector<T>>solve(int nr, int nc, const std::vector<std::vector<T>> &C) {const bool transpose = (nr > nc);if (!transpose) return _solve(nr, nc, C);std::vector trans(nc, std::vector<T>(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<int> 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_assignmentint main() {int H, W;cin >> H >> W;vector cost(W, vector<int>(W));REP(i, W) {int x, y;cin >> x >> y;REP(j, W) {const int h = x - 1;const int ylo = y - h, yhi = y;int ytgt = j + 1;int cost_row = 0;if (ytgt < ylo) cost_row = ylo - ytgt;if (yhi < ytgt) cost_row = ytgt - yhi;cost.at(i).at(j) = cost_row + h;}}dbg(cost);auto ret = linear_sum_assignment::solve(W, W, cost);dbg(ret);cout << get<0>(ret) << '\n';}