#include #include #include #include #include #include #include #include #include #include // #include "Src/Number/IntegerDivision.hpp" // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #include namespace zawa { namespace concepts { template concept Semigroup = requires { typename T::Element; { T::operation(std::declval(), std::declval()) } -> std::same_as; }; } // namespace concepts } // namespace zawa namespace zawa { namespace concepts { template concept Identitiable = requires { typename T::Element; { T::identity() } -> std::same_as; }; template concept Monoid = Semigroup and Identitiable; } // namespace } // namespace zawa #include #include #include namespace zawa { template class SegmentTree { public: using VM = Monoid; using V = typename VM::Element; using OM = Monoid; using O = typename OM::Element; SegmentTree() = default; explicit SegmentTree(usize n) : m_n{ n }, m_dat(n << 1, VM::identity()) {} explicit SegmentTree(const std::vector& dat) : m_n{ dat.size() }, m_dat(dat.size() << 1, VM::identity()) { for (usize i{} ; i < m_n ; i++) { m_dat[i + m_n] = dat[i]; } for (usize i{m_n} ; i-- ; ) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } [[nodiscard]] inline usize size() const noexcept { return m_n; } [[nodiscard]] V get(usize i) const { assert(i < size()); return m_dat[i + m_n]; } [[nodiscard]] V operator[](usize i) const { assert(i < size()); return m_dat[i + m_n]; } void operation(usize i, const O& value) { assert(i < size()); i += size(); m_dat[i] = OM::operation(m_dat[i], value); while (i = parent(i), i) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } void assign(usize i, const V& value) { assert(i < size()); i += size(); m_dat[i] = value; while (i = parent(i), i) { m_dat[i] = VM::operation(m_dat[left(i)], m_dat[right(i)]); } } [[nodiscard]] V product(u32 l, u32 r) const { assert(l <= r and r <= size()); V L{ VM::identity() }, R{ VM::identity() }; for (l += size(), r += size() ; l < r ; l = parent(l), r = parent(r)) { if (l & 1) { L = VM::operation(L, m_dat[l++]); } if (r & 1) { R = VM::operation(m_dat[--r], R); } } return VM::operation(L, R); } template requires std::predicate [[nodiscard]] usize maxRight(usize l, const F& f) { assert(l < size()); static_assert(std::is_convertible_v>, "maxRight's argument f must be function bool(T)"); assert(f(VM::identity())); usize res{l}, width{1}; V prod{ VM::identity() }; for (l += size() ; res + width <= size() ; l = parent(l), width <<= 1) if (l & 1) { if (not f(VM::operation(prod, m_dat[l]))) break; res += width; prod = VM::operation(prod, m_dat[l++]); } while (l = left(l), width >>= 1) { if (res + width <= size() and f(VM::operation(prod, m_dat[l]))) { res += width; prod = VM::operation(prod, m_dat[l++]); } } return res; } template requires std::predicate [[nodiscard]] usize minLeft(usize r, const F& f) const { assert(r <= size()); static_assert(std::is_convertible_v>, "minLeft's argument f must be function bool(T)"); assert(f(VM::identity())); usize res{r}, width{1}; V prod{ VM::identity() }; for (r += size() ; res >= width ; r = parent(r), width <<= 1) if (r & 1) { if (not f(VM::operation(m_dat[r - 1], prod))) break; res -= width; prod = VM::operation(prod, m_dat[--r]); } while (r = left(r), width >>= 1) { if (res >= width and f(VM::operation(m_dat[r - 1], prod))) { res -= width; prod = VM::operation(m_dat[--r], prod); } } return res; } friend std::ostream& operator<<(std::ostream& os, const SegmentTree& st) { for (usize i{1} ; i < 2 * st.size() ; i++) { os << st.m_dat[i] << (i + 1 == 2 * st.size() ? "" : " "); } return os; } private: constexpr u32 left(u32 v) const { return v << 1; } constexpr u32 right(u32 v) const { return v << 1 | 1; } constexpr u32 parent(u32 v) const { return v >> 1; } usize m_n; std::vector m_dat; }; } // namespace zawa // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // #include "Src/DataStructure/Heap/BinaryHeap.hpp" namespace zawa {} using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0 ; i < ssize(v) ; i++) os << v[i] << (i + 1 == ssize(v) ? "" : " "); return os; } /* * 注: 誤読していたので、B日働いて、C日休む場合で解いている */ const long long INF=(long long)-1e18; struct MAX { using Element = long long; static Element identity() { return INF; } static Element operation(Element L, Element R) { return max(L,R); } }; long long solve(int N,int B,int C,vector A) { vector S(N+1); for (int i = 0 ; i < N ; i++) S[i+1]=S[i]+A[i]; for (int i = 0 ; i < 10 ; i++) S.push_back(S.back()); SegmentTree dp(N),ep(N); for (int i = 0 ; i < B-1 ; i++) { long long kiyo=S[i+1]; dp.assign(i,kiyo-S[i+2]); ep.assign(i,kiyo); } for (int i = B-1 ; i < N ; i++) { long long kiyo=INF; if (i <= B+C-2) kiyo=max(kiyo,S[i+1]-S[max(0,i-B+2)]); kiyo=max(kiyo,dp.product(max(i-B,0),max(i-1,0))+S[i+1]); kiyo=max(kiyo,ep.product(max(i-B-C+2,0),max(i-B,0))+S[i+1]-S[i-B+2]); dp.assign(i,kiyo-S[i+2]); ep.assign(i,kiyo); } long long ans=INF; for (int i = 0 ; i < min(N,C) ; i++) ans=max(ans,ep[N-i-1]); return ans; } long long naive(int N,int B,int C,vector A) { vector S(N+1); for (int i = 0 ; i < N ; i++) S[i+1]=S[i]+A[i]; vector dp(N,INF); for (int i = 0 ; i < min(N,B) ; i++) dp[i]=S[i+1]; for (int i = 0 ; i < N ; i++) for (int j = 1 ; j < C ; j++) { long long sum=0; for (int k = 1 ; k < B and i + j + k < N ; k++) { sum+=A[i+j+k]; dp[i+j+k]=max(dp[i+j+k],dp[i]+sum); } } long long ans=INF; for (int i = 0 ; i < min(C,N) ; i++) ans=max(ans,dp[N-i-1]); return ans; } long long brute(int N,int B,int C,vector A) { vector col(N); auto dfs=[&](auto dfs,int i)->long long { if (i==N) { bool ok=1; for (int l = 0, r = 0 ; l < N ; l = r) { while (r < N and col[l] == col[r]) r++; if (col[l] == 1 and r-l >= B) ok=0; if (col[l] == 0 and r-l >= C) ok=0; } if (!ok) return INF; long long res=0; for (int j = 0 ; j < N ; j++) res+=col[j]*A[j]; return res; } long long ans=INF; col[i]=0; ans=max(ans,dfs(dfs,i+1)); col[i]=1; ans=max(ans,dfs(dfs,i+1)); return ans; }; return dfs(dfs,0); } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); #if !defined DEBUG int N,B,C; cin >> N >> B >> C; swap(B,C); vector A(N); for (auto& x : A) cin >> x; cout << solve(N,B,C,A) << '\n'; #else mt19937_64 mt{random_device{}()}; for (int testcase = 0 ; ; ) { cerr << "----------" << ++testcase << "----------" << endl; int N=mt()%7+1; int B=1,C=1; while (B == 1 or C == 1) { B=mt()%(N+1)+1; C=mt()%(N+1)+1; } vector A(N); for (long long& a : A) a = mt()%5+1; auto a = solve(N,C,B,A), b = brute(N,C,B,A); if (a != b) { // print testcase cout << N << ' ' << B << ' ' << C << '\n'; cout << A << endl; cerr << "you: " << a << endl; cout << "correct: " << b << endl; exit(0); } } #endif }