結果

問題 No.3306 Life is Easy?
ユーザー cho435
提出日時 2025-10-07 23:46:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,127 bytes
コンパイル時間 3,931 ms
コンパイル使用メモリ 269,228 KB
実行使用メモリ 15,944 KB
最終ジャッジ日時 2025-10-07 23:46:21
合計ジャッジ時間 17,854 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 4 -- * 31
権限があれば一括ダウンロードができます

ソースコード

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://sotanishy.github.io/cp-library-cpp/flow/min_cost_b_flow.hpp
template <typename Flow, typename Cost>
class MinCostFlow {
   public:
	MinCostFlow() = default;
	explicit MinCostFlow(int V) : V(V), G(V), b(V), potential(V) {
	}

	void add_supply(int v, Flow amount) {
		b[v] += amount;
	}
	void add_demand(int v, Flow amount) {
		b[v] -= amount;
	}

	void add_edge(int u, int v, Flow lb, Flow ub, Cost cost) {
		assert(lb <= ub);
		int e = G[u].size(), re = u == v ? e + 1 : G[v].size();
		G[u].push_back({v, re, ub, 0, cost});
		G[v].push_back({u, e, -lb, 0, -cost});
		edge_idx.push_back({u, e});
	}

	std::pair<bool, Cost> min_cost_flow() {
		// handle min flow constraints
		for (int v = 0; v < V; ++v) {
			for (auto& e : G[v]) {
				Flow f = e.residual_cap();
				if (f < 0) {
					b[v] -= f;
					b[e.to] += f;
					e.flow += f;
					G[e.to][e.rev].flow -= f;
				}
			}
		}

		// get max delta
		Flow max_cap = 1;
		for (int v = 0; v < V; ++v) {
			for (auto& e : G[v]) max_cap = std::max(max_cap, e.residual_cap());
		}
		Flow delta = 1;
		while (delta <= max_cap) delta <<= 1;

		std::vector<Cost> dist(V);
		std::vector<int> prevv(V), preve(V);
		using P = std::pair<Cost, int>;
		std::priority_queue<P, std::vector<P>, std::greater<P>> pq;

		for (delta >>= 1; delta > 0; delta >>= 1) {
			// handle negative edges
			for (int v = 0; v < V; ++v) {
				for (auto& e : G[v]) {
					Flow f = e.residual_cap();
					if (f >= delta && residual_cost(v, e) < 0) {
						b[v] -= f;
						b[e.to] += f;
						e.flow += f;
						G[e.to][e.rev].flow -= f;
					}
				}
			}

			while (true) {
				// dual
				dist.assign(V, INF);
				prevv.assign(V, -1);
				preve.assign(V, -1);
				for (int s = 0; s < V; ++s) {
					if (b[s] >= delta) {
						dist[s] = 0;
						pq.emplace(0, s);
					}
				}
				bool augment = false;
				Cost farthest = 0;
				while (!pq.empty()) {
					auto [d, v] = pq.top();
					pq.pop();
					if (dist[v] < d) continue;
					farthest = d;
					if (b[v] <= -delta) augment = true;
					for (int i = 0; i < (int)G[v].size(); ++i) {
						Edge& e = G[v][i];
						Cost ndist = dist[v] + residual_cost(v, e);
						if (e.residual_cap() >= delta && dist[e.to] > ndist) {
							dist[e.to] = ndist;
							prevv[e.to] = v;
							preve[e.to] = i;
							pq.emplace(dist[e.to], e.to);
						}
					}
				}

				for (int v = 0; v < V; ++v)
					potential[v] += std::min(dist[v], farthest);

				if (!augment) break;

				// primal
				for (int t = 0; t < V; ++t) {
					if (b[t] >= 0 || dist[t] > farthest) continue;

					Flow f = -b[t];
					int v;
					for (v = t; prevv[v] != -1 && f >= delta; v = prevv[v]) {
						f = std::min(f, G[prevv[v]][preve[v]].residual_cap());
					}
					f = std::min(f, b[v]);

					if (f < delta) continue;
					for (v = t; prevv[v] != -1; v = prevv[v]) {
						Edge& e = G[prevv[v]][preve[v]];
						e.flow += f;
						G[v][e.rev].flow -= f;
					}

					b[t] += f;
					b[v] -= f;
				}
			}
		}

		Cost res = 0;
		for (int v = 0; v < V; ++v) {
			for (auto& e : G[v]) {
				res += e.flow * e.cost;
			}
		}
		res /= 2;

		bool feasible = true;
		for (int v = 0; v < V; ++v) {
			if (b[v] != 0) {
				feasible = false;
				break;
			}
		}

		return {feasible, res};
	}

	std::vector<Flow> get_flow() const {
		std::vector<Flow> ret(edge_idx.size());
		for (int j = 0; j < (int)edge_idx.size(); ++j) {
			auto [v, i] = edge_idx[j];
			ret[j] = G[v][i].flow;
		}
		return ret;
	}

	std::vector<Cost> get_potential() const {
		return potential;
	}

   private:
	struct Edge {
		int to, rev;
		Flow cap, flow;
		Cost cost;

		Flow residual_cap() const {
			return cap - flow;
		}
	};

	static constexpr Cost INF = std::numeric_limits<Cost>::max() / 2;

	int V;
	std::vector<std::vector<Edge>> G;
	std::vector<Flow> b;
	std::vector<Cost> potential;
	std::vector<std::pair<int, int>> edge_idx;

	Cost residual_cost(int v, const Edge& e) const {
		return e.cost + potential[v] - potential[e.to];
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	MinCostFlow<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) {
		g.add_edge(n * m + i, st, 0, 1, 0);
		g.add_edge(st, n * m + i, 0, 1, 0);
	}
	rep(i, 0, m) {
		rep(j, 0, n - 1) {
			g.add_edge(i * n + j, i * n + j + 1, 0, n, a[i][j] - a[i][j + 1]);
		}
		rep(j, 0, n) {
			g.add_edge(n * m + j, i * n + j, 0, 1, 0);
			g.add_edge(i * n + j, n * m + j, 0, 1, 0);
		}
	}
	auto [f, cs] = g.min_cost_flow();
	assert(f);
	cout << -cs << '\n';
}

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