結果
| 問題 |
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';
}