結果
| 問題 | No.957 植林 |
| ユーザー |
 nanophoto12
|
| 提出日時 | 2021-03-03 00:52:46 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,977 bytes |
| コンパイル時間 | 4,781 ms |
| コンパイル使用メモリ | 278,388 KB |
| 実行使用メモリ | 36,300 KB |
| 最終ジャッジ日時 | 2024-10-03 03:04:03 |
| 合計ジャッジ時間 | 8,628 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
10,496 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | TLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
ソースコード
#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846 // pi
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void chmax(T& reference, T value) {
reference = max(reference, value);
}
template<typename T>
void chmaxmap(map<T, T>& m, T key, T value) {
if (m.count(key)) {
chmax(m[key], value);
}
else {
m[key] = value;
}
}
template<typename T>
void chmin(T& reference, T value) {
reference = min(reference, value);
}
#include <atcoder/all>
using namespace atcoder;
struct MaxFlowCalculator {
typedef ll flow_type;
//g.first...cost
//g.second..dest
ll max_flow(int s, int t, const vector<vector<pair<flow_type, flow_type>>>& g) {
struct edge_ { flow_type to, cap, rev; };
vector<bool> used(g.size(), false);
vector<vector<edge_>> G(g.size());
for (int i = 0; i < g.size(); i++) for (int j = 0; j < g[i].size(); j++)
{
flow_type from = i, to = g[i][j].second;
flow_type cap = g[i][j].first;
G[from].push_back({ to, cap, (flow_type)G[to].size() });
G[to].push_back({ from, 0, (flow_type)G[from].size() - 1 });
}
auto dfs = [&](auto&& f, flow_type v, flow_type t, flow_type fl)->int {
if (v == t) return fl;
used[v] = true;
rep(i, G[v].size()) {
edge_& e = G[v][i];
if (!used[e.to] && e.cap > 0) {
flow_type d = f(f, e.to, t, min(fl, e.cap));
if (d > 0) {
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0LL;
};
flow_type flow = 0;
while (1) {
used.assign(used.size(), false);
flow_type f = dfs(dfs, s, t, 1e18);
if (f == 0) return flow;
flow += f;
}
}
};
int main() {
int h, w;
cin >> h >> w;
vector<vector<ll>> grid(h, vector<ll>(w));
rep(y, h) {
rep(x, w){
cin >> grid[y][x];
}
}
vector<ll> rows(h), cols(w);
rep(i, h) cin >> rows[i];
rep(i, w) cin >> cols[i];
vector < vector<pair<ll, ll>>> graph(h*w + h*2 + w * 2 + 2);
const int start = h * w + h * 2 + w * 2;
const int goal = start + 1;
const int rs = h * w;
const int cs = h * w + 2 * h;
rep(y, h) {
rep(x, w) {
int id = y * w + x;
graph[start].emplace_back(grid[y][x], id);
int xline = cs + x * 2;
int yline = rs + y * 2;
graph[id].emplace_back(1e16, xline);
graph[id].emplace_back(1e16, yline);
}
}
rep(y, h) {
int yline = rs + y * 2;
graph[yline].emplace_back(rows[y], yline + 1);
graph[yline+1].emplace_back(1e16, goal);
}
rep(x, w) {
int xline = cs + x * 2;
graph[xline].emplace_back(cols[x], xline + 1);
graph[xline + 1].emplace_back(1e16, goal);
}
ll sum = 0;
rep(y, h) {
sum += rows[y];
}
rep(x, w) {
sum += cols[x];
}
MaxFlowCalculator f;
auto a = f.max_flow(start, goal, graph);
cout << sum - a << endl;
return 0;
}