#877845 (C++17) No.957 植林

提出ソース

結果

問題	No.957 植林
ユーザー	👑 Nachia
提出日時	2023-06-03 15:16:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	300 ms / 2,000 ms
コード長	9,286 bytes
コンパイル時間	1,524 ms
コンパイル使用メモリ	100,144 KB
実行使用メモリ	13,892 KB
最終ジャッジ日時	2024-06-09 03:36:19
合計ジャッジ時間	9,696 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	32 ms 11,852 KB
testcase_04	AC	31 ms 11,408 KB
testcase_05	AC	32 ms 12,296 KB
testcase_06	AC	40 ms 12,756 KB
testcase_07	AC	37 ms 11,672 KB
testcase_08	AC	19 ms 12,248 KB
testcase_09	AC	20 ms 12,056 KB
testcase_10	AC	21 ms 12,580 KB
testcase_11	AC	20 ms 12,108 KB
testcase_12	AC	21 ms 12,084 KB
testcase_13	AC	15 ms 11,232 KB
testcase_14	AC	18 ms 12,852 KB
testcase_15	AC	19 ms 12,156 KB
testcase_16	AC	17 ms 11,088 KB
testcase_17	AC	17 ms 11,780 KB
testcase_18	AC	223 ms 12,188 KB
testcase_19	AC	230 ms 12,184 KB
testcase_20	AC	240 ms 12,636 KB
testcase_21	AC	252 ms 12,788 KB
testcase_22	AC	264 ms 12,868 KB
testcase_23	AC	273 ms 13,300 KB
testcase_24	AC	281 ms 13,548 KB
testcase_25	AC	286 ms 13,836 KB
testcase_26	AC	292 ms 13,880 KB
testcase_27	AC	287 ms 13,552 KB
testcase_28	AC	283 ms 13,512 KB
testcase_29	AC	285 ms 13,864 KB
testcase_30	AC	281 ms 13,460 KB
testcase_31	AC	221 ms 12,100 KB
testcase_32	AC	231 ms 12,184 KB
testcase_33	AC	235 ms 12,592 KB
testcase_34	AC	254 ms 12,656 KB
testcase_35	AC	257 ms 12,864 KB
testcase_36	AC	274 ms 13,300 KB
testcase_37	AC	282 ms 13,548 KB
testcase_38	AC	293 ms 13,840 KB
testcase_39	AC	300 ms 13,892 KB
testcase_40	AC	292 ms 13,552 KB
testcase_41	AC	16 ms 13,792 KB
testcase_42	AC	18 ms 13,520 KB
testcase_43	AC	18 ms 13,316 KB
testcase_44	AC	18 ms 13,440 KB
testcase_45	AC	2 ms 6,940 KB
testcase_46	AC	2 ms 6,944 KB
testcase_47	AC	1 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード