結果
問題 | No.957 植林 |
ユーザー | ianCK |
提出日時 | 2019-12-27 09:08:14 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,397 bytes |
コンパイル時間 | 516 ms |
コンパイル使用メモリ | 47,488 KB |
実行使用メモリ | 23,268 KB |
最終ジャッジ日時 | 2024-04-16 10:35:50 |
合計ジャッジ時間 | 5,684 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,888 KB |
testcase_01 | AC | 3 ms
5,760 KB |
testcase_02 | AC | 3 ms
5,888 KB |
testcase_03 | AC | 105 ms
18,088 KB |
testcase_04 | AC | 82 ms
17,384 KB |
testcase_05 | AC | 89 ms
18,476 KB |
testcase_06 | AC | 99 ms
19,016 KB |
testcase_07 | AC | 111 ms
17,756 KB |
testcase_08 | AC | 64 ms
18,216 KB |
testcase_09 | AC | 60 ms
18,324 KB |
testcase_10 | AC | 73 ms
18,880 KB |
testcase_11 | AC | 67 ms
18,324 KB |
testcase_12 | AC | 64 ms
18,164 KB |
testcase_13 | AC | 49 ms
16,080 KB |
testcase_14 | AC | 71 ms
19,368 KB |
testcase_15 | AC | 60 ms
18,036 KB |
testcase_16 | AC | 48 ms
16,200 KB |
testcase_17 | AC | 54 ms
17,452 KB |
testcase_18 | TLE | - |
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 | -- | - |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:77:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 77 | scanf("%d%d", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:78:72: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 78 | for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &g[i][j]); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:79:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | for (int i = 1; i <= n; i++) scanf("%d", &r[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:80:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 80 | for (int i = 1; i <= m; i++) scanf("%d", &c[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <vector> #include <queue> using namespace std; #define PB push_back constexpr int kN = int(1E5 + 10), kNN = int(3E2 + 10); constexpr long long int kInf = (long long int) (1E16 + 10); struct Edge { int to, rev; long long int cap; }; vector<Edge> graph[kN]; int dep[kN], went[kN], iter[kN]; void AddEdge(int u, int v, long long int c) { graph[u].PB({v, int(graph[v].size()), c}); graph[v].PB({u, int(graph[u].size()) - 1, 0}); return ; } void bfs(int s, int t) { int nxt; queue<int> q; q.push(s); iter[s] = dep[s] = 0; went[s] = t; while (!q.empty()) { nxt = q.front(); q.pop(); for (Edge i : graph[nxt]) if (went[i.to] != t && i.cap > 0) { q.push(i.to); went[i.to] = t; dep[i.to] = dep[nxt] + 1; iter[i.to] = 0; } } return ; } long long int dfs(int u, int t, long long int nv) { if (u == t) return nv; int temp; for (int &i = iter[u]; i < int(graph[u].size()); i++) { Edge& nxt = graph[u][i]; if (nxt.cap > 0 && dep[nxt.to] > dep[u]) { temp = dfs(nxt.to, t, min(nv, nxt.cap)); if (temp > 0) { nxt.cap -= temp; graph[nxt.to][nxt.rev].cap += temp; return temp; } } } return 0; } long long int dinic(int s, int t) { long long int ans = 0, f; int cnt = 0; for (int i = 0; i < kN; i++) went[i] = cnt; while (true) { bfs(s, ++cnt); if (went[s] != went[t]) break; while ((f = dfs(s, t, kInf)) > 0) ans += f; } return ans; } int g[kNN][kNN], r[kNN], c[kNN]; int main() { int n, m, s, t, nxt = 1; long long int ans = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &g[i][j]); for (int i = 1; i <= n; i++) scanf("%d", &r[i]); for (int i = 1; i <= m; i++) scanf("%d", &c[i]); s = 0; t = n * m + n + m + 1; for (int i = 1; i <= n; i++) ans += r[i]; for (int i = 1; i <= m; i++) ans += c[i]; for (int i = 1; i <= n; i++, nxt++) AddEdge(s, nxt, r[i]); nxt += m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++, nxt++) { AddEdge(nxt, t, g[i][j]); AddEdge(i, nxt, min(r[i], g[i][j])); } ans -= dinic(s, t); nxt = n + 1; for (int i = 1; i <= m; i++, nxt++) AddEdge(s, nxt, c[i]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++, nxt++) AddEdge(j + n, nxt, min(c[j], g[i][j])); printf("%lld\n", ans - dinic(s, t)); }