#line 1 "kyopro/main.cpp" #include #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; using i3 = array; using i4 = array; using f2 = array; using f3 = array; using f4 = array; template using min_pq = priority_queue, greater>; template using max_pq = priority_queue, less>; 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::max(); } static constexpr result_type min() { return numeric_limits::min(); } private: result_type a, b, c, d; }; xor_shift_128 xorrand; template istream& operator>>(istream& is, array& a) { for (auto& x : a) is >> x; return is; } template ostream& operator<<(ostream& os, const array& a) { for (size_t i = 0; i < N; i++) os << (i ? " " : "") << a[i]; return os; } template istream& operator>>(istream& is, vector& v) { for (auto& x : v) is >> x; return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < (int)v.size(); i++) os << (i ? " " : "") << v[i]; return os; } template ostream& operator<<(ostream& os, const vector>& 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 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 void print(sep sp, const Args&... args) { int i = 0; ((cout << (i++ ? sp.s : "") << args), ...); cout << "\n"; } template void print(const Args&... args) { print(sep{" "}, args...); } template void print(const vector& v) { for (int i = 0; i < (int)v.size(); i++) cout << (i ? " " : "") << v[i]; cout << "\n"; } template void print(sep sp, const vector& 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 struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} explicit lazy_segtree(int n) : lazy_segtree(vector(n, e())) {} explicit lazy_segtree(const vector& v) : _n(int(v.size())) { size = (int)bit_ceil((unsigned int)(_n)); log = countr_zero((unsigned int)size); d = vector(2 * size, e()); lz = vector(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 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 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 d; vector 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 A(N); cin >> A; chmin(B, 3); using r = range_add_range_max; lazy_segtree seg(N + B + C - 2); ll off = N; seg.set(off + B - 2, 0); seg.set(off + B - 3, 0); for (int i = 0; i < N; i++) { dbg(off); if (B == 3) { seg.set(off - 1, seg.get(off + 1)); seg.set(off, max(seg.get(off), seg.prod(off + 2, off + B + C - 2))); } else { seg.set(off - 1, seg.prod(off + 1, off + B + C - 2)); } off--; seg.apply(off + B - 1, off + B + C - 2, A[i]); dbg(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; }