#1192606 (C++23) No.3760 Streaming Schedule

• 問題: No.3760 Streaming Schedule
• ユーザー: besukohu
• 提出日時: 2026-10-09 23:49:06
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,047 ms / 2,000 ms
• コード長: 9,242 bytes
• コンパイル時間: 2,201 ms
• コンパイル使用メモリ: 346,084 KB
• 実行使用メモリ: 34,976 KB
• 最終ジャッジ日時: 2026-10-09 23:49:28
• 合計ジャッジ時間: 15,668 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

#line 1 "kyopro/main.cpp"
#include <bits/stdc++.h>

#line 3 "kyopro_lib/base.hpp"

#line 5 "kyopro_lib/base.hpp"

using namespace std;
using ll = long long;
using ld = long double;

using i2 = array<ll, 2>;
using i3 = array<ll, 3>;
using i4 = array<ll, 4>;

using f2 = array<ld, 2>;
using f3 = array<ld, 3>;
using f4 = array<ld, 4>;

template <class T>
using min_pq = priority_queue<T, vector<T>, greater<T>>;

template <class T>
using max_pq = priority_queue<T, vector<T>, less<T>>;

const ll INF = (1LL << 61);

bool chmin(auto& a, const auto& b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, const auto& b) { return a < b ? a = b, 1 : 0; }

ll floor_div(ll a, ll b) { return a / b - (a % b != 0 && (a ^ b) < 0); }
ll ceil_div(ll a, ll b) { return a / b + (a % b != 0 && (a ^ b) > 0); }
ll floor_mod(ll a, ll b) { return a % b + (a % b != 0 && (a ^ b) < 0) * b; }

mt19937 mt(time(0));
class xor_shift_128 {
   public:
    typedef uint32_t result_type;
    xor_shift_128(result_type seed = mt()) {
        set_seed(seed);
    }
    void set_seed(result_type seed) {
        a = seed = 1812433253 * (seed ^ (seed >> 30));
        b = seed = 1812433253 * (seed ^ (seed >> 30)) + 1;
        c = seed = 1812433253 * (seed ^ (seed >> 30)) + 2;
        d = seed = 1812433253 * (seed ^ (seed >> 30)) + 3;
    }
    result_type gen() {
        result_type t = (a ^ (a << 11));
        a = b;
        b = c;
        c = d;
        return d = (d ^ (d >> 19)) ^ (t ^ (t >> 8));
    }
    result_type operator()() {
        return gen();
    }
    ll gen_range(ll min_inclusive, ll max_exclusive) {
        ll diff = max_exclusive - min_inclusive;
        assert(diff);
        return min_inclusive + gen() % diff;
    }

    static constexpr result_type max() { return numeric_limits<result_type>::max(); }
    static constexpr result_type min() { return numeric_limits<result_type>::min(); }

   private:
    result_type a, b, c, d;
};
xor_shift_128 xorrand;

template <class T, size_t N>
istream& operator>>(istream& is, array<T, N>& a) {
    for (auto& x : a) is >> x;
    return is;
}
template <class T, size_t N>
ostream& operator<<(ostream& os, const array<T, N>& a) {
    for (size_t i = 0; i < N; i++)
        os << (i ? " " : "") << a[i];
    return os;
}

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        os << (i ? " " : "") << v[i];
    return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<vector<T>>& vv) {
    for (int i = 0; i < (int)vv.size(); i++)
        os << (i ? "\n" : "") << vv[i];
    return os;
}

#define dbg(...) cerr << #__VA_ARGS__ << " = ", debug_print(__VA_ARGS__);
void debug_print() { cerr << endl; }
template <class T, class... Args>
void debug_print(const T& x, const Args&... args) {
    cerr << x;
    if constexpr (sizeof...(args) > 0) cerr << ", ";
    debug_print(args...);
}

struct sep {
    const char* s;
    sep(const char* s) : s(s) {}
};

template <class... Args>
void print(sep sp, const Args&... args) {
    int i = 0;
    ((cout << (i++ ? sp.s : "") << args), ...);
    cout << "\n";
}

template <class... Args>
void print(const Args&... args) {
    print(sep{" "}, args...);
}

template <class T>
void print(const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        cout << (i ? " " : "") << v[i];
    cout << "\n";
}

template <class T>
void print(sep sp, const vector<T>& v) {
    for (int i = 0; i < (int)v.size(); i++)
        cout << (i ? sp.s : "") << v[i];
    cout << "\n";
}
#line 4 "kyopro/main.cpp"

bool is_multi = false;

ll mod = 998244353;

template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct lazy_segtree {
   public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(vector<S>(n, e())) {}
    explicit lazy_segtree(const vector<S>& v) : _n(int(v.size())) {
        size = (int)bit_ceil((unsigned int)(_n));
        log = countr_zero((unsigned int)size);
        d = vector<S>(2 * size, e());
        lz = vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    void set(int p, S x) {
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        if (l == r) return e();
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() {
        return d[1];
    }

    void apply(int l, int r, F f) {
        if (l == r) return;
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <class G>
    int max_right(int l, G g) {
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <class G>
    int min_left(int r, G g) {
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

   private:
    int _n, size, log;
    vector<S> d;
    vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

struct range_add_range_max {
    using value_t = ll;
    using lazy_t = ll;
    static value_t op(value_t a, value_t b) { return max(a, b); }
    static value_t e() { return -INF; }
    static value_t mapping(lazy_t f, value_t x) { return x + f; }
    static lazy_t composition(lazy_t f, lazy_t g) { return f + g; }
    static lazy_t id() { return 0; }
};

void solve() {
    ll N, B, C;
    cin >> N >> B >> C;
    vector<ll> A(N);
    cin >> A;

    chmin(B, 3);

    using r = range_add_range_max;
    lazy_segtree<r::value_t, r::op, r::e, r::lazy_t, r::mapping, r::composition, r::id> seg(N + B + C - 2);

    ll off = N;

    seg.set(off + B - 2, 0);
    seg.set(off + B - 1, 0);

    for (int i = 0; i < N; i++) {
        dbg(off);
        if (B == 3) {
            seg.set(off - 1, seg.get(off + 1));
            seg.set(off + 1, max(seg.get(off), seg.get(off + 1)));
            seg.set(off, max(seg.get(off), seg.prod(off + 2, off + B + C - 2)));
        } else {
            seg.set(off, max(seg.get(off - 1), seg.get(off)));
            seg.set(off - 1, seg.prod(off + 1, off + B + C - 2));
        }
        off--;
        seg.apply(off + B - 1, off + B + C - 2, A[i]);

        // for (int j = off; j < off + B + C - 2; j++) {
        //     dbg(i, j, seg.get(j));
        // }
    }

    cout << seg.all_prod() << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    ll tests = 1;
    if (is_multi) {
        cin >> tests;
    }

    while (tests--) {
        solve();
    }

    return 0;
}