結果
| 問題 | No.957 植林 |
| コンテスト | |
| ユーザー |
 drken1215
|
| 提出日時 | 2026-09-07 01:49:24 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,093 ms / 2,000 ms |
| + 655µs | |
| コード長 | 17,449 bytes |
| 記録 | |
| コンパイル時間 | 3,378 ms |
| コンパイル使用メモリ | 388,436 KB |
| 実行使用メモリ | 17,984 KB |
| 最終ジャッジ日時 | 2026-09-07 01:50:07 |
| 合計ジャッジ時間 | 23,263 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 45 |
ソースコード
// code template is in https://github.com/drken1215/algorithm/blob/master/template_minimum.cpp
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
//------------------------------//
// Utility
//------------------------------//
using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }
#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
// input
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
// output
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
const vector<int> DX = {1, 0, -1, 0, 1, -1, 1, -1};
const vector<int> DY = {0, 1, 0, -1, 1, -1, -1, 1};
// 1, 2, 3-variable submodular optimization
/*
N 個の bool 変数 x_0, x_1, ..., x_{N-1} について、以下の形のコストが定められたときの最小コストを求める
・1 変数 xi に関するコスト (1 変数劣モジュラ関数)
xi = F のときのコスト, xi = T のときのコスト
・2 変数 xi, xj 間の関係性についてのコスト (2 変数劣モジュラ関数)
(xi, xj) = (F, F): コスト A
(xi, xj) = (F, T): コスト B
(xi, xj) = (T, F): コスト C
(xi, xj) = (T, T): コスト D
(ただし、B + C >= A + D でなければならない)
・よくある例は、A = B = D = 0, C >= 0 の形である (特に関数化している)
・この場合は、特に Project Selection Problem と呼ばれ、俗に「燃やす埋める」などとも呼ばれる
・xi = T, xj = F のときにコスト C がかかる
・他に面白い例として、A = B = C = 0, D <= 0 の形もある (これも関数化している)
・xi = T, xj = T のときに (-D) の利得が得られる
・3 変数 xi, xj, xk 間の関係性についてのコスト (3 変数劣モジュラ関数)
(xi, xj, xk) = (F, F, F): コスト A
(xi, xj, xk) = (F, F, T): コスト B
(xi, xj, xk) = (F, T, F): コスト C
(xi, xj, xk) = (F, T, T): コスト D
(xi, xj, xk) = (T, F, F): コスト E
(xi, xj, xk) = (T, F, T): コスト F
(xi, xj, xk) = (T, T, F): コスト G
(xi, xj, xk) = (T, T, T): コスト H
*/
// 1, 2, 3-variable submodular optimization
template<class COST> struct ThreeVariableSubmodularOpt {
// constructors
ThreeVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {}
ThreeVariableSubmodularOpt(int n, COST inf = numeric_limits<COST>::max() / 2)
: N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {}
// initializer
void init(int n, COST inf = numeric_limits<COST>::max() / 2) {
N = n, S = n, T = n + 1;
OFFSET = 0, INF = inf;
list.clear();
list.resize(N + 2);
pos.clear();
}
// add constant cost
void add_cost(COST cost) {
OFFSET += cost;
}
// add 1-variable submodular function
void add_single_cost(int xi, COST false_cost, COST true_cost) {
assert(0 <= xi && xi < N);
if (false_cost >= true_cost) {
OFFSET += true_cost;
if (false_cost - true_cost > 0) add_edge(S, xi, false_cost - true_cost);
} else {
OFFSET += false_cost;
add_edge(xi, T, true_cost - false_cost);
}
}
void add_single_cost_01(int xi, COST false_cost, COST true_cost) {
add_single_cost(xi, false_cost, true_cost);
}
void add_single_cost_10(int xi, COST false_cost, COST true_cost) {
add_single_cost(xi, true_cost, false_cost);
}
// add "project selection" constraint
// xi = T, xj = F: strictly prohibited
void add_psp_constraint(int xi, int xj) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
add_edge(xi, xj, INF);
}
void add_psp_constraint_01(int xi, int xj) {
add_psp_constraint(xj, xi);
}
void add_psp_constraint_10(int xi, int xj) {
add_psp_constraint(xi, xj);
}
// add "project selection" penalty
// xi = T, xj = F: cost C
void add_psp_penalty(int xi, int xj, COST C) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(C >= 0);
if (C > 0) add_edge(xi, xj, C);
}
void add_psp_penalty_01(int xi, int xj, COST C) {
add_psp_penalty(xj, xi, C);
}
void add_psp_penalty_10(int xi, int xj, COST C) {
add_psp_penalty(xi, xj, C);
}
// add both True profit
// xi = T, xj = T: profit P (cost -P)
void add_both_true_profit(int xi, int xj, COST P) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(P >= 0);
OFFSET -= P;
if (P > 0) add_edge(S, xi, P);
if (P > 0) add_edge(xi, xj, P);
}
// add both False profit
// xi = F, xj = F: profit P (cost -P)
void add_both_false_profit(int xi, int xj, COST P) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(P >= 0);
OFFSET -= P;
if (P > 0) add_edge(xj, T, P);
if (P > 0) add_edge(xi, xj, P);
}
// add general 2-variable submodular function
// (xi, xj) = (F, F): A, (F, T): B
// (xi, xj) = (T, F): C, (T, T): D
void add_submodular_function(int xi, int xj, COST A, COST B, COST C, COST D) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(xi != xj);
assert(B + C >= A + D); // assure submodular function
OFFSET += A;
add_single_cost(xi, 0, D - B);
add_single_cost(xj, 0, B - A);
if (B + C - A - D > 0) add_psp_penalty(xi, xj, B + C - A - D);
}
// add all True profit
// y = F: not gain profit (= cost is P), T: gain profit (= cost is 0)
// y: T, xi: F is prohibited
void add_all_true_profit(const vector<int> &xs, COST P) {
assert(P >= 0);
int y = (int)list.size();
list.resize(y + 1);
OFFSET -= P;
add_edge(S, y, P);
for (auto xi : xs) {
assert(xi >= 0 && xi < N);
add_edge(y, xi, INF);
}
}
// add all False profit
// y = F: gain profit (= cost is 0), T: not gain profit (= cost is P)
// xi = T, y = F is prohibited
void add_all_false_profit(const vector<int> &xs, COST P) {
assert(P >= 0);
int y = (int)list.size();
list.resize(y + 1);
OFFSET -= P;
add_edge(y, T, P);
for (auto xi : xs) {
assert(xi >= 0 && xi < N);
add_edge(xi, y, INF);
}
}
// add general 3-variable submodular function
// (xi, xj, xk) = (F, F, F): cost A
// (xi, xj, xk) = (F, F, T): cost B
// (xi, xj, xk) = (F, T, F): cost C
// (xi, xj, xk) = (F, T, T): cost D
// (xi, xj, xk) = (T, F, F): cost E
// (xi, xj, xk) = (T, F, T): cost F
// (xi, xj, xk) = (T, T, F): cost G
// (xi, xj, xk) = (T, T, T): cost H
void add_submodular_function(int xi, int xj, int xk,
COST A, COST B, COST C, COST D,
COST E, COST F, COST G, COST H) {
assert(0 <= xi && xi < N);
assert(0 <= xj && xj < N);
assert(0 <= xk && xk < N);
COST P = (A + D + F + G) - (B + C + E + H);
COST P12 = (C + E) - (A + G), P13 = (D + G) - (C + H);
COST P21 = (D + F) - (B + H), P23 = (B + C) - (A + D);
COST P31 = (B + E) - (A + F), P32 = (F + G) - (E + H);
assert(P12 >= 0 && P21 >= 0);
assert(P23 >= 0 && P32 >= 0);
assert(P31 >= 0 && P13 >= 0);
if (P >= 0) {
OFFSET += A;
add_single_cost(xi, 0, F - B);
add_single_cost(xj, 0, G - E);
add_single_cost(xk, 0, D - C);
add_psp_penalty(xj, xi, P12);
add_psp_penalty(xk, xj, P23);
add_psp_penalty(xi, xk, P31);
add_all_true_profit({xi, xj, xk}, P);
} else {
OFFSET += H;
add_single_cost(xi, C - G, 0);
add_single_cost(xj, B - D, 0);
add_single_cost(xk, E - F, 0);
add_psp_penalty(xi, xj, P21);
add_psp_penalty(xj, xk, P32);
add_psp_penalty(xk, xi, P13);
add_all_false_profit({xi, xj, xk}, -P);
}
}
// solve
COST solve() {
return dinic() + OFFSET;
}
// reconstrcut the optimal assignment
vector<bool> reconstruct() {
vector<bool> res(N, false), seen(list.size(), false);
queue<int> que;
seen[S] = true;
que.push(S);
while (!que.empty()) {
int v = que.front();
que.pop();
for (const auto &e : list[v]) {
if (e.cap > 0 && !seen[e.to]) {
if (e.to < N) res[e.to] = true;
seen[e.to] = true;
que.push(e.to);
}
}
}
return res;
}
// debug
friend ostream& operator << (ostream& s, const ThreeVariableSubmodularOpt &tvs) {
const auto &edges = tvs.get_edges();
for (const auto &e : edges) s << e << endl;
return s;
}
private:
// edge class
struct Edge {
// core members
int rev, from, to;
COST cap;
// constructor
Edge(int r, int f, int t, COST c) : rev(r), from(f), to(t), cap(c) {}
// debug
friend ostream& operator << (ostream& s, const Edge& e) {
return s << e.from << "->" << e.to << '(' << e.cap << ')';
}
};
// inner data
int N, S, T;
COST OFFSET, INF;
vector<vector<Edge>> list;
vector<pair<int,int>> pos;
// add edge
Edge &get_rev_edge(const Edge &e) {
return list[e.to][e.rev];
}
Edge &get_edge(int i) {
return list[pos[i].first][pos[i].second];
}
const Edge &get_edge(int i) const {
return list[pos[i].first][pos[i].second];
}
vector<Edge> get_edges() const {
vector<Edge> edges;
for (int i = 0; i < (int)pos.size(); ++i) {
edges.push_back(get_edge(i));
}
return edges;
}
void add_edge(int from, int to, COST cap) {
if (cap <= 0) return;
pos.emplace_back(from, (int)list[from].size());
list[from].push_back(Edge((int)list[to].size(), from, to, cap));
list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0));
}
// Dinic's algorithm
COST dinic(COST limit_flow) {
COST current_flow = 0;
vector<int> level((int)list.size(), -1), iter((int)list.size(), 0);
queue<int> que;
// Dinic BFS
auto bfs = [&]() -> void {
fill(level.begin(), level.end(), -1);
level[S] = 0;
while (!que.empty()) que.pop();
que.push(S);
while (!que.empty()) {
int v = que.front();
que.pop();
for (const Edge &e : list[v]) {
if (level[e.to] < 0 && e.cap > 0) {
level[e.to] = level[v] + 1;
if (e.to == T) return;
que.push(e.to);
}
}
}
};
// Dinic DFS
auto dfs = [&](auto self, int v, COST up_flow) {
if (v == S) return up_flow;
COST res_flow = 0;
for (int &i = iter[v]; i < (int)list[v].size(); i++) {
Edge &e = list[v][i], &re = get_rev_edge(e);
if (level[v] <= level[e.to] || re.cap <= 0) continue;
COST flow = self(self, e.to, min(up_flow - res_flow, re.cap));
if (flow <= 0) continue;
res_flow += flow;
e.cap += flow, re.cap -= flow;
if (res_flow == up_flow) return res_flow;
}
level[v] = (int)list.size();
return res_flow;
};
// flow
while (current_flow < limit_flow) {
bfs();
if (level[T] < 0) break;
fill(iter.begin(), iter.end(), 0);
while (current_flow < limit_flow) {
COST flow = dfs(dfs, T, limit_flow - current_flow);
if (flow <= 0) break;
current_flow += flow;
}
}
return current_flow;
};
COST dinic() {
return dinic(numeric_limits<COST>::max() / 2);
}
};
//------------------------------//
// Solver
//------------------------------//
/*
x[i] := i 行目をとるなら 1 (-R[i])、とらないなら 0 (0)
y[j] := j 列目をとるなら 1 (-C[j])、とらないなら 0 (0)
x[i] = 0 かつ y[j] = 0 ならば、コスト 0
x[i] = 1 または y[j] = 1 ならば、コスト G[i][j]
*/
int main() {
ll H, W;
cin >> H >> W;
vvll G(H, vll(W));
vll R(H), C(W);
cin >> G >> R >> C;
ThreeVariableSubmodularOpt<ll> opt(H + W);
REP(i, H) opt.add_single_cost_10(i, -R[i], 0);
REP(j, W) opt.add_single_cost_10(j+H, -C[j], 0);
REP(i, H) REP(j, W) opt.add_submodular_function(i, j+H, 0, G[i][j], G[i][j], G[i][j]);
cout << -opt.solve() << endl;
}