Submit Info #65342

Problem Lang User Status Time Memory
Assignment Problem cpp fastred AC 146 ms 2.40 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
hand_minus_00 AC 146 ms 2.37 MiB
hand_plus_00 AC 145 ms 2.37 MiB
max_random_00 AC 42 ms 2.37 MiB
max_random_01 AC 37 ms 2.32 MiB
max_random_02 AC 37 ms 2.40 MiB
max_random_03 AC 43 ms 2.37 MiB
max_random_04 AC 41 ms 2.32 MiB
random_00 AC 5 ms 0.70 MiB
random_01 AC 6 ms 0.78 MiB
random_02 AC 2 ms 0.53 MiB
random_03 AC 6 ms 0.68 MiB
random_04 AC 1 ms 0.45 MiB

#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define all(x) x.begin(), x.end() #define forn(i, a, b) for(int i = int(a); i <= int(b); ++i) #define rep(i, n) forn(i, 0, n - 1) #define revforn(i, a, b) for(int i = int(a); i >= int(b); --i) #define rev(i, n) revforn(i, n - 1, 0) #define trav(it, x) for(auto& it : x) #define pb push_back #define mp make_pair #define eb emplace_back #define ff first #define ss second template<class T> using vt = vector<T>; template<class T> using vvt = vt<vt<T>>; template<class T> using pr = pair<T, T>; template <typename T> istream& operator >>(istream& is, vt<T>& v) {const size_t n = v.size(); for (size_t i = 0; i < n; ++i) is >> v[i]; return is;} template <typename T> ostream& operator <<(ostream& os, const vt<T>& v) {const size_t n = v.size(); for (size_t i = 0; i < n; ++i) {if (i != 0) os << ' '; os << v[i];} return os;} template <typename T> istream& operator >> (istream& is, vvt<T>& vv) {const size_t n = vv.size(); const size_t m = vv[0].size(); for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < m; ++j) is >> vv[i][j]; return is;} template <typename T> ostream& operator << (ostream& os, const vvt<T>& vv) {const size_t n = vv.size(); const size_t m = vv[0].size(); for (size_t i = 0; i < n; ++i) {if (i != 0) os << '\n'; for (size_t j = 0; j < m; ++j) {if (j != 0) os << ' '; os << vv[i][j];}} return os;} template <typename T, typename U> istream& operator >>(istream& is, pair<T, U>& p) {is >> p.first >> p.second; return is;} template <typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U>& p) { os << p.first << ' ' << p.second; return os;} template <class A, class B> string to_string(pair<A, B> p); template <class A, class B, class C> string to_string(tuple<A, B, C> p); template <class A, class B, class C, class D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) {return '"' + s + '"';} string to_string(const char* s) {return to_string((string) s);} string to_string(const char& c) {return (string)"" + c;} string to_string(bool b) {return (b ? "true" : "false");} string to_string(vector<bool> v) {bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) res += ", "; first = false; res += to_string(v[i]);} res += "}"; return res;} template <size_t N> string to_string(bitset<N> v) {string res = ""; for (size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]); return res;} template <class A> string to_string(A v) {bool first = true; string res = "{"; for (const auto& x : v) {if (!first) res += ", "; first = false; res += to_string(x);} res += "}"; return res;} template <class A, class B> string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";} template <class A, class B, class C> string to_string(tuple<A, B, C> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";} template <class A, class B, class C, class D> string to_string(tuple<A, B, C, D> p) {return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";} void debug_out() {cerr << endl;} template <class Head, class... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);} #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template<class T, class U> bool chmax(T& a, U b) {if (a < b) {a = b; return true;} else return false;} template<class T, class U> bool chmin(T& a, U b) {if (b < a) {a = b; return true;} else return false;} template<typename T> class Hungarian { public: int n; int m; vector<vector<T>> a; vector<T> u; vector<T> v; vector<int> pa; vector<int> pb; vector<int> way; vector<T> minv; vector<bool> used; T inf; Hungarian(int _n, int _m) : n(_n), m(_m) { assert(n <= m); a = vector<vector<T>>(n, vector<T>(m)); u = vector<T>(n + 1); v = vector<T>(m + 1); pa = vector<int>(n + 1, -1); pb = vector<int>(m + 1, -1); way = vector<int>(m, -1); minv = vector<T>(m); used = vector<bool>(m + 1); inf = numeric_limits<T>::max(); } inline void add_row(int i) { fill(minv.begin(), minv.end(), inf); fill(used.begin(), used.end(), false); pb[m] = i; pa[i] = m; int j0 = m; do { used[j0] = true; int i0 = pb[j0]; T delta = inf; int j1 = -1; for (int j = 0; j < m; j++) { if (!used[j]) { T cur = a[i0][j] - u[i0] - v[j]; if (cur < minv[j]) { minv[j] = cur; way[j] = j0; } if (minv[j] < delta) { delta = minv[j]; j1 = j; } } } for (int j = 0; j <= m; j++) { if (used[j]) { u[pb[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while (pb[j0] != -1); do { int j1 = way[j0]; pb[j0] = pb[j1]; pa[pb[j0]] = j0; j0 = j1; } while (j0 != m); } inline T current_score() { return -v[m]; } inline T solve() { for (int i = 0; i < n; i++) { add_row(i); } return current_score(); } }; int32_t main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; cin >> n; Hungarian<ll>hg(n, n); rep(i, n) { rep(j, n) { ll x; cin >> x; hg.a[i][j] = x; } } cout << hg.solve() << '\n'; rep(i, n)cout<<hg.pa[i] << ' '; return 0; }