結果
問題 |
No.3306 Life is Easy?
|
ユーザー |
![]() |
提出日時 | 2025-10-05 15:45:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 13,052 bytes |
コンパイル時間 | 4,075 ms |
コンパイル使用メモリ | 312,044 KB |
実行使用メモリ | 113,872 KB |
最終ジャッジ日時 | 2025-10-05 15:45:57 |
合計ジャッジ時間 | 10,520 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 34 |
ソースコード
// https://judge.yosupo.jp/submission/81021 #line 1 "library/Template/template.hpp" #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define ALL(v) (v).begin(), (v).end() using ll = long long int; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #line 2 "library/Utility/fastio.hpp" #include <unistd.h> class FastIO { static constexpr int L = 1 << 16; char rdbuf[L]; int rdLeft = 0, rdRight = 0; inline void reload() { int len = rdRight - rdLeft; memmove(rdbuf, rdbuf + rdLeft, len); rdLeft = 0, rdRight = len; rdRight += fread(rdbuf + len, 1, L - len, stdin); } inline bool skip() { for (;;) { while (rdLeft != rdRight and rdbuf[rdLeft] <= ' ') rdLeft++; if (rdLeft == rdRight) { reload(); if (rdLeft == rdRight) return false; } else break; } return true; } template <typename T, enable_if_t<is_integral<T>::value, int> = 0> inline bool _read(T& x) { if (!skip()) return false; if (rdLeft + 20 >= rdRight) reload(); bool neg = false; if (rdbuf[rdLeft] == '-') { neg = true; rdLeft++; } x = 0; while (rdbuf[rdLeft] >= '0' and rdLeft < rdRight) { x = x * 10 + (neg ? -(rdbuf[rdLeft++] ^ 48) : (rdbuf[rdLeft++] ^ 48)); } return true; } template <typename T, enable_if_t<is_floating_point<T>::value, int> = 0> inline bool _read(T& x) { if (!skip()) return false; if (rdLeft + 20 >= rdRight) reload(); bool neg = false; if (rdbuf[rdLeft] == '-') { neg = true; rdLeft++; } x = 0; while (rdbuf[rdLeft] >= '0' and rdbuf[rdLeft] <= '9' and rdLeft < rdRight) { x = x * 10 + (rdbuf[rdLeft++] ^ 48); } if (rdbuf[rdLeft] != '.') return true; rdLeft++; T base = .1; while (rdbuf[rdLeft] >= '0' and rdbuf[rdLeft] <= '9' and rdLeft < rdRight) { x += base * (rdbuf[rdLeft++] ^ 48); base *= .1; } if (neg) x = -x; return true; } inline bool _read(char& x) { if (!skip()) return false; if (rdLeft + 1 >= rdRight) reload(); x = rdbuf[rdLeft++]; return true; } inline bool _read(string& x) { if (!skip()) return false; for (;;) { int pos = rdLeft; while (pos < rdRight and rdbuf[pos] > ' ') pos++; x.append(rdbuf + rdLeft, pos - rdLeft); if (rdLeft == pos) break; rdLeft = pos; if (rdLeft == rdRight) reload(); else break; } return true; } template <typename T> inline bool _read(vector<T>& v) { for (auto& x : v) { if (!_read(x)) return false; } return true; } char wtbuf[L], tmp[50]; int wtRight = 0; inline void flush() { fwrite(wtbuf, 1, wtRight, stdout); wtRight = 0; } inline void _write(const char& x) { if (wtRight > L - 32) flush(); wtbuf[wtRight++] = x; } inline void _write(const string& x) { for (auto& c : x) _write(c); } template <typename T, enable_if_t<is_integral<T>::value, int> = 0> inline void _write(T x) { if (wtRight > L - 32) flush(); if (x == 0) { _write('0'); return; } else if (x < 0) { _write('-'); if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x = -x; } int pos = 0; while (x != 0) { tmp[pos++] = char((x % 10) | 48); x /= 10; } rep(i, 0, pos) wtbuf[wtRight + i] = tmp[pos - 1 - i]; wtRight += pos; } template <typename T> inline void _write(const vector<T>& v) { rep(i, 0, v.size()) { if (i) _write(' '); _write(v[i]); } } public: FastIO() {} ~FastIO() { flush(); } inline void read() {} template <typename Head, typename... Tail> inline void read(Head& head, Tail&... tail) { assert(_read(head)); read(tail...); } template <bool ln = true, bool space = false> inline void write() { if (ln) _write('\n'); } template <bool ln = true, bool space = false, typename Head, typename... Tail> inline void write(const Head& head, const Tail&... tail) { if (space) _write(' '); _write(head); write<ln, true>(tail...); } }; /** * @brief Fast IO */ #line 3 "sol.cpp" // reference: http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf class GeneralWeightedMatching { struct E { int u, v; ll w; }; int n, m, in; vector<vector<E>> G; vector<int> mate, slack, root, par, isS, used; vector<vector<int>> flower, belong; vector<ll> dual; queue<int> que; ll dist(const E& e) { return dual[e.u] + dual[e.v] - e.w; } void update(int u, int v) { if (!slack[v] or dist(G[u][v]) < dist(G[slack[v]][v])) slack[v] = u; } void recalc(int v) { slack[v] = 0; rep(i, 1, n + 1) if (G[i][v].w and root[i] != v and isS[root[i]] == 1) update(i, v); } void push(int v) { if (v <= n) que.push(v); else for (auto& nxt : flower[v]) push(nxt); } void set(int v, int rt) { root[v] = rt; if (v > n) for (auto& nxt : flower[v]) set(nxt, rt); } int findeven(int b, int v) { int pos = find(ALL(flower[b]), v) - flower[b].begin(); if (pos & 1) { reverse(flower[b].begin() + 1, flower[b].end()); pos = flower[b].size() - pos; } return pos; } void match(int u, int v) { mate[u] = G[u][v].v; if (u > n) { int x = belong[u][G[u][v].u]; int pos = findeven(u, x); rep(i, 0, pos) match(flower[u][i], flower[u][i ^ 1]); match(x, v); rotate(flower[u].begin(), flower[u].begin() + pos, flower[u].end()); } } void link(int u, int v) { for (;;) { int nv = root[mate[u]]; match(u, v); if (!nv) break; v = nv, u = root[par[nv]]; match(v, u); } } void make(int u, int v, int lca) { int id = n + 1; while (id <= m and root[id]) id++; if (id > m) m++; flower[id].clear(); rep(i, 1, m + 1) G[id][i].w = G[i][id].w = 0; rep(i, 1, n + 1) belong[id][i] = 0; isS[id] = 1, dual[id] = 0, mate[id] = mate[lca]; while (u != lca) { flower[id].push_back(u); u = root[mate[u]]; push(u); flower[id].push_back(u); u = root[par[u]]; } flower[id].push_back(lca); reverse(ALL(flower[id])); while (v != lca) { flower[id].push_back(v); v = root[mate[v]]; push(v); flower[id].push_back(v); v = root[par[v]]; } set(id, id); for (auto& c : flower[id]) { rep(i, 1, m + 1) if (!G[id][i].w or dist(G[c][i]) < dist(G[id][i])) { G[id][i] = G[c][i], G[i][id] = G[i][c]; } rep(i, 1, n + 1) if (belong[c][i]) belong[id][i] = c; } recalc(id); } void expand(int b) { for (auto& c : flower[b]) set(c, c); int x = belong[b][G[b][par[b]].u]; isS[x] = 2, par[x] = par[b]; int pos = findeven(b, x); for (int i = 0; i < pos; i += 2) { int T = flower[b][i], S = flower[b][i + 1]; isS[S] = 1, isS[T] = 2; par[T] = G[S][T].u; slack[S] = slack[T] = 0; push(S); } rep(i, pos + 1, flower[b].size()) { isS[flower[b][i]] = 0; recalc(flower[b][i]); } flower[b].clear(); root[b] = 0; } bool path(const E& e) { int u = root[e.u], v = root[e.v]; if (!isS[v]) { par[v] = e.u; isS[v] = 2; int nu = root[mate[v]]; slack[v] = slack[nu] = 0; isS[nu] = 1; push(nu); } else if (isS[v] == 1) { int lca = 0, bu = u, bv = v; in++; while (bu) { used[bu] = in; bu = root[mate[bu]]; if (bu) bu = root[par[bu]]; } while (bv) { if (used[bv] == in) { lca = bv; break; } bv = root[mate[bv]]; if (bv) bv = root[par[bv]]; } if (lca) make(u, v, lca); else { link(u, v), link(v, u); return true; } } return false; } bool augment() { isS = slack = par = vector<int>(n * 2); que = queue<int>(); rep(i, 1, m + 1) if (root[i] == i and !mate[i]) { isS[i] = 1; push(i); } if (que.empty()) return false; for (;;) { while (!que.empty()) { int v = que.front(); que.pop(); rep(i, 1, n + 1) if (G[v][i].w and root[i] != root[v]) { if (!dist(G[v][i])) { if (path(G[v][i])) return true; } else if (isS[root[i]] != 2) update(v, root[i]); } } ll delta = INF; rep(i, n + 1, m + 1) if (root[i] == i and isS[i] == 2) chmin(delta, dual[i] / 2); rep(i, 1, m + 1) if (root[i] == i and slack[i] and isS[i] != 2) { if (!isS[i]) chmin(delta, dist(G[slack[i]][i])); else chmin(delta, dist(G[slack[i]][i]) / 2); } rep(i, 1, n + 1) { if (isS[root[i]] == 1) { dual[i] -= delta; if (dual[i] <= 0) return false; } else if (isS[root[i]] == 2) dual[i] += delta; } rep(i, n + 1, m + 1) if (root[i] == i and isS[i]) { if (isS[i] == 1) dual[i] += delta * 2; else dual[i] -= delta * 2; } rep(i, 1, m + 1) if (root[i] == i and slack[i] and root[slack[i]] != i) { if (dist(G[slack[i]][i]) == 0 and path(G[slack[i]][i])) return true; } rep(i, n + 1, m + 1) if (root[i] == i and isS[i] == 2 and dual[i] == 0) expand(i); } } public: GeneralWeightedMatching(int _n) : n(_n), m(n), in(0), G(n * 2, vector<E>(n * 2)), mate(n * 2), root(n * 2), used(n * 2), flower(n * 2), belong(n * 2, vector<int>(n * 2)), dual(n * 2) { rep(i, 0, n + 1) { root[i] = i; belong[i][i] = i; if (i) dual[i] = INF; rep(j, 0, n + 1) G[i][j] = E{i, j, 0}; } } void add_edge(int u, int v, ll w) { u++, v++; chmax(G[u][v].w, w * 2); chmax(G[v][u].w, w * 2); } vector<int> run() { while (augment()); vector<int> res(n, -1); rep(i, 1, n + 1) if (mate[i]) res[i - 1] = mate[i] - 1; return res; } }; FastIO io; int main() { int n, m; cin >> n >> m; vector a(n, vector<int>(m)); rep(i, 0, n) rep(j, 0, m) cin >> a[i][j]; vector b(n, vector<int>(n)); GeneralWeightedMatching G(n); rep(i, 0, n) rep(j, i + 1, n) { int r = 0; rep(k, 0, m) chmax(r, a[j][k] - a[i][k]); G.add_edge(i, j, r); b[i][j] = r; } auto res = G.run(); ll ans = 0; rep(i, 0, n) if (res[i] > i) { ans += b[i][res[i]]; } cout << ans << '\n'; }