#include <bits/stdc++.h> using namespace std; // long long solve(int l, int r, const vector<long long>& pref, const int& k) { vector<long long> dp(r-l+2); for (int i = l; i <= r; ++i) { auto& cdp = dp[i-l+1]; cdp = dp[i-l]; if (i-l+1-k >= 0) cdp = max(cdp, dp[i-l+1-k] + pref[i] - pref[i-k]); } return dp.back(); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, q; cin >> n >> k >> q; vector<long long> v(n+1); for (int i = 1; i <= n; ++i) cin >> v[i]; partial_sum(begin(v), end(v), begin(v)); while (q--) { int l, r; cin >> l >> r; cout << solve(l, r, v, k) << '\n'; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <bits/stdc++.h> using namespace std; // long long solve(int l, int r, const vector<long long>& pref, const int& k) { vector<long long> dp(r-l+2); for (int i = l; i <= r; ++i) { auto& cdp = dp[i-l+1]; cdp = dp[i-l]; if (i-l+1-k >= 0) cdp = max(cdp, dp[i-l+1-k] + pref[i] - pref[i-k]); } return dp.back(); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k, q; cin >> n >> k >> q; vector<long long> v(n+1); for (int i = 1; i <= n; ++i) cin >> v[i]; partial_sum(begin(v), end(v), begin(v)); while (q--) { int l, r; cin >> l >> r; cout << solve(l, r, v, k) << '\n'; } } |