結果
| 問題 | No.957 植林 |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2023-06-03 15:16:03 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 336 ms / 2,000 ms |
| コード長 | 9,286 bytes |
| コンパイル時間 | 2,215 ms |
| コンパイル使用メモリ | 99,064 KB |
| 実行使用メモリ | 13,748 KB |
| 最終ジャッジ日時 | 2023-08-28 07:55:40 |
| 合計ジャッジ時間 | 11,975 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 37 ms
11,780 KB |
| testcase_04 | AC | 34 ms
11,212 KB |
| testcase_05 | AC | 33 ms
12,116 KB |
| testcase_06 | AC | 42 ms
12,608 KB |
| testcase_07 | AC | 38 ms
11,444 KB |
| testcase_08 | AC | 20 ms
12,024 KB |
| testcase_09 | AC | 19 ms
12,016 KB |
| testcase_10 | AC | 22 ms
12,372 KB |
| testcase_11 | AC | 21 ms
12,000 KB |
| testcase_12 | AC | 21 ms
11,740 KB |
| testcase_13 | AC | 16 ms
10,928 KB |
| testcase_14 | AC | 21 ms
12,648 KB |
| testcase_15 | AC | 19 ms
11,860 KB |
| testcase_16 | AC | 16 ms
10,928 KB |
| testcase_17 | AC | 17 ms
11,432 KB |
| testcase_18 | AC | 244 ms
11,904 KB |
| testcase_19 | AC | 248 ms
12,004 KB |
| testcase_20 | AC | 261 ms
12,512 KB |
| testcase_21 | AC | 277 ms
12,556 KB |
| testcase_22 | AC | 293 ms
12,540 KB |
| testcase_23 | AC | 297 ms
13,032 KB |
| testcase_24 | AC | 316 ms
13,532 KB |
| testcase_25 | AC | 332 ms
13,688 KB |
| testcase_26 | AC | 329 ms
13,720 KB |
| testcase_27 | AC | 330 ms
13,280 KB |
| testcase_28 | AC | 324 ms
13,248 KB |
| testcase_29 | AC | 328 ms
13,720 KB |
| testcase_30 | AC | 336 ms
13,188 KB |
| testcase_31 | AC | 243 ms
11,852 KB |
| testcase_32 | AC | 258 ms
12,008 KB |
| testcase_33 | AC | 270 ms
12,500 KB |
| testcase_34 | AC | 277 ms
12,444 KB |
| testcase_35 | AC | 281 ms
12,536 KB |
| testcase_36 | AC | 296 ms
13,012 KB |
| testcase_37 | AC | 307 ms
13,528 KB |
| testcase_38 | AC | 319 ms
13,696 KB |
| testcase_39 | AC | 323 ms
13,716 KB |
| testcase_40 | AC | 327 ms
13,248 KB |
| testcase_41 | AC | 16 ms
13,748 KB |
| testcase_42 | AC | 17 ms
13,224 KB |
| testcase_43 | AC | 17 ms
13,148 KB |
| testcase_44 | AC | 18 ms
13,140 KB |
| testcase_45 | AC | 1 ms
4,380 KB |
| testcase_46 | AC | 2 ms
4,376 KB |
| testcase_47 | AC | 2 ms
4,380 KB |
ソースコード
#line 1 "..\\Main.cpp"
#include <atcoder/maxflow>
#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\misc\\nyaanio.hpp"
#include <cstring>
#include <type_traits>
#include <utility>
#include <cstdio>
#include <string>
#include <cstdint>
namespace fastio {
static constexpr int SZ = 1 << 17;
char inbuf[SZ], outbuf[SZ];
int in_left = 0, in_right = 0, out_right = 0;
struct Pre {
char num[40000];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i * 4 + j] = n % 10 + '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
int len = in_right - in_left;
memmove(inbuf, inbuf + in_left, len);
in_right = len + fread(inbuf + len, 1, SZ - len, stdin);
in_left = 0;
if(in_right != SZ) inbuf[in_right] = '\000';
}
inline void flush() {
fwrite(outbuf, 1, out_right, stdout);
out_right = 0;
}
inline void skip_space() {
if (in_left + 32 > in_right) load();
while (inbuf[in_left] <= ' ') in_left++;
}
inline void rd(char& c) {
if (in_left + 32 > in_right) load();
c = inbuf[in_left++];
}
template <typename T>
inline void rd(T& x) {
if (in_left + (int)sizeof(T) * 8 > in_right) load();
char c;
do c = inbuf[in_left++];
while (c < '-');
[[maybe_unused]] bool minus = false;
if constexpr (std::is_signed<T>::value == true) {
if (c == '-') minus = true, c = inbuf[in_left++];
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = inbuf[in_left++];
}
if constexpr (std::is_signed<T>::value == true) {
if (minus) x = -x;
}
}
inline void wt(char c) {
if (out_right > SZ - 32) flush();
outbuf[out_right++] = c;
}
inline void wt(bool b) {
if (out_right > SZ - 32) flush();
outbuf[out_right++] = b ? '1' : '0';
}
inline void wt(const std::string &s) {
if (out_right + s.size() > SZ - 32) flush();
if (s.size() > SZ - 32){ fwrite(s.c_str(), 1, s.size(), stdout); return; }
memcpy(outbuf + out_right, s.data(), sizeof(char) * s.size());
out_right += s.size();
}
inline void wt(const char* s) {
wt(std::string(s));
}
template <typename T>
inline void wt(T x) {
if (out_right > SZ - (int)sizeof(T) * 8) flush();
if (!x) {
outbuf[out_right++] = '0';
return;
}
if constexpr (std::is_signed<T>::value == true) {
if (x < 0) outbuf[out_right++] = '-', x = -x;
}
constexpr int SZT = sizeof(T) * 8;
int i = SZT - 4;
char buf[SZT];
while (x >= 10000) {
memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
x /= 10000;
i -= 4;
}
if (x < 100) {
if (x < 10) {
outbuf[out_right] = '0' + x;
++out_right;
} else {
uint32_t q = (uint32_t(x) * 205) >> 11;
uint32_t r = uint32_t(x) - q * 10;
outbuf[out_right] = '0' + q;
outbuf[out_right + 1] = '0' + r;
out_right += 2;
}
} else {
if (x < 1000) {
memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3);
out_right += 3;
} else {
memcpy(outbuf + out_right, pre.num + (x << 2), 4);
out_right += 4;
}
}
memcpy(outbuf + out_right, buf + i + 4, SZT - 4 - i);
out_right += SZT - 4 - i;
}
} // namespace fastio
namespace nachia{
struct CInStream{} cin;
template <typename T>
inline CInStream& operator>>(CInStream& c, T& dest){ fastio::rd(dest); return c; }
struct COutStream{
~COutStream(){ atexit(fastio::flush); }
} cout;
template <typename T>
inline COutStream& operator<<(COutStream& c, const T& src){ fastio::wt(src); return c; }
} // namespace nachia
#line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\vec.hpp"
#include <vector>
#include <iterator>
#include <algorithm>
template<class Elem> struct seq;
struct iotai;
template<class Iter>
struct seq_view{
using Ref = typename std::iterator_traits<Iter>::reference;
using Elem = typename std::iterator_traits<Iter>::value_type;
Iter a, b;
Iter begin() const { return a; }
Iter end() const { return b; }
int size() const { return (int)(b-a); }
seq_view(Iter first, Iter last) : a(first), b(last) {}
seq_view sort() const { std::sort(a, b); return *this; }
Ref& operator[](int x){ return *(a+x); }
template<class F, class ret = seq<int>> ret sorti(F f) const {
ret x(iotai(0), iotai(size()));
x().sort([&](int l, int r){ return f(a[l],a[r]); });
return x;
}
template<class ret = seq<Elem>> ret col() const { return ret(begin(), end()); }
template<class F> seq_view sort(F f) const { std::sort(a, b, f); return *this; }
Iter uni() const { return std::unique(a, b); }
Iter lb(const Elem& x) const { return std::lower_bound(a, b, x); }
Iter ub(const Elem& x) const { return std::upper_bound(a, b, x); }
template<class F> Iter lb(const Elem& x, F f) const { return std::lower_bound(a, b, x, f); }
template<class F> Iter ub(const Elem& x, F f) const { return std::upper_bound(a, b, x, f); }
template<class F> Iter when_true_to_false(F f) const {
if(a == b) return a;
return std::lower_bound(a, b, *a,
[&](const Elem& x, const Elem& y){ return f(x); });
}
seq_view same(Elem x) const { return { lb(x), ub(x) }; }
template<class F> auto map(F f) const {
seq<typename Iter::value_type> r;
for(auto& x : *this) r.emp(f(x));
return r;
}
Iter max() const { return std::max_element(a, b); }
Iter min() const { return std::min_element(a, b); }
seq_view rev() const { std::reverse(a, b); return *this; }
};
struct iotai {
using i64 = long long;
using Me = iotai;
using value_type = i64;
using iterator_category = std::random_access_iterator_tag;
using difference_type = ptrdiff_t;
using pointer = i64*;
using reference = i64&;
i64 x;
iotai(i64 y) : x(y) {}
i64 operator*() const { return x; }
std::size_t operator-(Me a) const { return x - a.x; }
Me operator++(){ return { (i64)(++x) }; }
Me operator--(){ return { (i64)(--x) }; }
Me operator++(int){ return { (i64)(x++) }; }
Me operator--(int){ return { (i64)(x--) }; }
Me operator+(std::size_t a) const { return { (i64)(x+a) }; }
Me operator-(std::size_t a) const { return { (i64)(x-a) }; }
static seq_view<iotai> range(i64 l, i64 r){ return { Me{l}, Me{r} }; }
};
template<class Elem>
struct seq {
using Base = typename std::vector<Elem>;
using Iter = typename Base::iterator;
using CIter = typename Base::const_iterator;
using View = seq_view<Iter>;
using CView = seq_view<CIter>;
seq(){}
explicit seq(int n, const Elem& value = Elem()) : a(0<n?n:0, value) {}
template <class I2> seq(I2 first, I2 last) : a(first, last) {}
seq(std::initializer_list<Elem> il) : a(std::move(il)) {}
operator Base() const { return a; }
Iter begin(){ return a.begin(); }
CIter begin() const { return a.begin(); }
Iter end(){ return a.end(); }
CIter end() const { return a.end(); }
int size() const { return a.size(); }
seq sortunied(){ seq x = *this; x().sort(); x.a.erase(x().uni(), x.end()); return x; }
Iter operator()(int x){ return (x < 0 ? a.end() : a.begin()) + x; }
CIter operator()(int x) const { return (x < 0 ? a.end() : a.begin()) + x; }
View operator()(int l, int r){ return { (*this)(l), (*this)(r) }; }
CView operator()(int l, int r) const { return { (*this)(l), (*this)(r) }; }
View operator()(){ return (*this)(0,size()); }
CView operator()() const { return (*this)(0,size()); }
Elem& operator[](int x){ return *((*this)(x)); }
const Elem& operator[](int x) const { return *((*this)(x)); }
Base& operator*(){ return a; }
const Base& operator*() const { return a; }
template<class... Args>
seq& emp(Args &&... args){
a.emplace_back(std::forward<Args>(args) ...);
return *this;
}
template<class Range>
seq& app(Range& x){ for(auto& v : a) emp(v); }
Elem pop(){
Elem x = std::move(a.back());
a.pop_back(); return x;
}
Base a;
};
#line 4 "..\\Main.cpp"
using i64 = long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
int main(){
using nachia::cin;
using nachia::cout;
int H, W; cin >> H >> W;
seq<seq<i64>> G;
rep(y,H){
G.emp(W);
rep(x,W) cin >> G[y][x];
}
seq<i64> R(H), C(W);
rep(y,H) cin >> R[y];
rep(x,W) cin >> C[x];
atcoder::mf_graph<i64> mf(H+W+2);
int src = H + W;
int snk = H + W + 1;
i64 off = 0;
rep(y,H){
i64 c = -R[y] * 2;
rep(x,W) c += G[y][x];
if(c < 0){ mf.add_edge(src, y, -c); off -= c; }
if(c > 0){ mf.add_edge(y, snk, c); }
}
rep(x,W){
i64 c = -C[x] * 2;
rep(y,H) c += G[y][x];
if(c < 0){ mf.add_edge(src, H+x, -c); off -= c; }
if(c > 0){ mf.add_edge(H+x, snk, c); }
}
rep(y,H) rep(x,W){
mf.add_edge(H+x, y, G[y][x]);
mf.add_edge(y, H+x, G[y][x]);
}
i64 ans = mf.flow(src, snk);
ans = (off - ans) / 2;
cout << ans << '\n';
return 0;
}