結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

// 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';
}
0