結果

問題 No.3306 Life is Easy?
ユーザー cho435
提出日時 2025-10-08 00:20:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,118 bytes
コンパイル時間 4,858 ms
コンパイル使用メモリ 259,900 KB
実行使用メモリ 136,140 KB
最終ジャッジ日時 2025-10-08 00:20:34
合計ジャッジ時間 17,826 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 3 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

using mint = atcoder::modint998244353;

// https://hitonanode.github.io/cplib-cpp/flow/mcf_costscaling.hpp
// Cost scaling
// https://people.orie.cornell.edu/dpw/orie633/
template <class Cap, class Cost, int SCALING = 1, int REFINEMENT_ITER = 20>
struct mcf_costscaling {
	mcf_costscaling() = default;
	mcf_costscaling(int n) : _n(n), to(n), b(n), p(n) {
	}

	int _n;
	std::vector<Cap> cap;
	std::vector<Cost> cost;
	std::vector<int> opposite;
	std::vector<std::vector<int>> to;
	std::vector<Cap> b;
	std::vector<Cost> p;

	int add_edge(int from_, int to_, Cap cap_, Cost cost_) {
		assert(0 <= from_ and from_ < _n);
		assert(0 <= to_ and to_ < _n);
		assert(0 <= cap_);
		cost_ *= (_n + 1);
		const int e = int(cap.size());
		to[from_].push_back(e);
		cap.push_back(cap_);
		cost.push_back(cost_);
		opposite.push_back(to_);

		to[to_].push_back(e + 1);
		cap.push_back(0);
		cost.push_back(-cost_);
		opposite.push_back(from_);
		return e / 2;
	}
	void add_supply(int v, Cap supply) {
		b[v] += supply;
	}
	void add_demand(int v, Cap demand) {
		add_supply(v, -demand);
	}

	template <typename RetCost = Cost> RetCost solve() {
		Cost eps = 1;
		std::vector<int> que;
		for (const auto c : cost) {
			while (eps <= -c) eps <<= SCALING;
		}
		for (; eps >>= SCALING;) {
			auto no_admissible_cycle = [&]() -> bool {
				for (int i = 0; i < _n; i++) {
					if (b[i]) return false;
				}
				std::vector<Cost> pp = p;
				for (int iter = 0; iter < REFINEMENT_ITER; iter++) {
					bool flg = false;
					for (int e = 0; e < int(cap.size()); e++) {
						if (!cap[e]) continue;
						int i = opposite[e ^ 1], j = opposite[e];
						if (pp[j] > pp[i] + cost[e] + eps)
							pp[j] = pp[i] + cost[e] + eps, flg = true;
					}
					if (!flg) return p = pp, true;
				}
				return false;
			};
			if (no_admissible_cycle()) continue;  // Refine

			for (int e = 0; e < int(cap.size()); e++) {
				const int i = opposite[e ^ 1], j = opposite[e];
				const Cost cp_ij = cost[e] + p[i] - p[j];
				if (cap[e] and cp_ij < 0)
					b[i] -= cap[e], b[j] += cap[e], cap[e ^ 1] += cap[e],
						cap[e] = 0;
			}
			que.clear();
			int qh = 0;
			for (int i = 0; i < _n; i++) {
				if (b[i] > 0) que.push_back(i);
			}
			std::vector<int> iters(_n);
			while (qh < int(que.size())) {
				const int i = que[qh++];
				for (; iters[i] < int(to[i].size()) and b[i];
					 ++iters[i]) {	// Push
					int e = to[i][iters[i]];
					if (!cap[e]) continue;
					int j = opposite[e];
					Cost cp_ij = cost[e] + p[i] - p[j];
					if (cp_ij >= 0) continue;
					Cap f = b[i] > cap[e] ? cap[e] : b[i];
					if (b[j] <= 0 and b[j] + f > 0) que.push_back(j);
					b[i] -= f, b[j] += f, cap[e] -= f, cap[e ^ 1] += f;
				}

				if (b[i] > 0) {	 // Relabel
					bool flg = false;
					for (int e : to[i]) {
						if (!cap[e]) continue;
						Cost x = p[opposite[e]] - cost[e] - eps;
						if (!flg or x > p[i]) flg = true, p[i] = x;
					}
					que.push_back(i), iters[i] = 0;
				}
			}
		}
		RetCost ret = 0;
		for (int e = 0; e < int(cap.size()); e += 2)
			ret += RetCost(cost[e]) * cap[e ^ 1];
		return ret / (_n + 1);
	}
	std::vector<Cost> potential() const {
		std::vector<Cost> ret = p, c0 = cost;
		for (auto& x : ret) x /= (_n + 1);
		for (auto& x : c0) x /= (_n + 1);
		while (true) {
			bool flg = false;
			for (int i = 0; i < _n; i++) {
				for (const auto e : to[i]) {
					if (!cap[e]) continue;
					int j = opposite[e];
					auto y = ret[i] + c0[e];
					if (ret[j] > y) ret[j] = y, flg = true;
				}
			}
			if (!flg) break;
		}
		return ret;
	}
	struct edge {
		int from, to;
		Cap cap, flow;
		Cost cost;
	};
	edge get_edge(int e) const {
		int m = cap.size() / 2;
		assert(e >= 0 and e < m);
		return {opposite[e * 2 + 1], opposite[e * 2],
				cap[e * 2] + cap[e * 2 + 1], cap[e * 2 + 1],
				cost[e * 2] / (_n + 1)};
	}
	std::vector<edge> edges() const {
		int m = cap.size() / 2;
		std::vector<edge> result(m);
		for (int i = 0; i < m; i++) result[i] = get_edge(i);
		return result;
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	mcf_costscaling<ll, ll> g(n * m + n + 1);
	int st = n * m + n;
	vector<vector<int>> a(m, vector<int>(n));
	rep(i, 0, n) rep(j, 0, m) cin >> a[j][i];
	rep(i, 0, n / 2) {
		g.add_edge(st, n * m + i, 1, 0);
	}
	rep(i, n / 2, n) {
		g.add_edge(n * m + i, st, 1, 0);
	}
	rep(i, 0, m) {
		rep(j, 0, n - 1) {
			g.add_edge(i * n + j, i * n + j + 1, n, a[i][j] - a[i][j + 1]);
		}
		rep(j, 0, n) {
			g.add_edge(n * m + j, i * n + j, 1, 0);
			g.add_edge(i * n + j, n * m + j, 1, 0);
		}
	}
	auto res = g.solve<__int128>();
	cout << -(ll)res << '\n';
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0