#include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 3e5 + 7; int n, k, q, l, r, d; int t[NMAX]; //long long ans; long long pref[NMAX]; long long dpp() { vector<long long> dp(d + 1); dp[k - 1] = max(0LL, pref[l + k - 1] - pref[l - 1]); for (int i = k; i < d; ++i) { dp[i] = max(dp[i - 1], max(0LL, pref[l + i] - pref[l + i - k]) + dp[i - k]); } return dp[d - 1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> q; for (int i = 1; i <= n; ++i) { cin >> t[i]; } for (int i = 1; i <= n; ++i) { pref[i] = t[i] + pref[i - 1]; } for (int i = 0; i < q; ++i) { cin >> l >> r; d = r - l + 1; if (k > d) { cout << 0 << "\n"; } /*else if (k < 2 * d) { tree(); }*/ else { cout << dpp() << "\n"; } } return 0; }
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include <bits/stdc++.h> using namespace std; #ifdef D #define DEBUG(x) \ do { \ x \ cout.flush(); \ } while (0) #else #define DEBUG(x) #endif const int NMAX = 3e5 + 7; int n, k, q, l, r, d; int t[NMAX]; //long long ans; long long pref[NMAX]; long long dpp() { vector<long long> dp(d + 1); dp[k - 1] = max(0LL, pref[l + k - 1] - pref[l - 1]); for (int i = k; i < d; ++i) { dp[i] = max(dp[i - 1], max(0LL, pref[l + i] - pref[l + i - k]) + dp[i - k]); } return dp[d - 1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> q; for (int i = 1; i <= n; ++i) { cin >> t[i]; } for (int i = 1; i <= n; ++i) { pref[i] = t[i] + pref[i - 1]; } for (int i = 0; i < q; ++i) { cin >> l >> r; d = r - l + 1; if (k > d) { cout << 0 << "\n"; } /*else if (k < 2 * d) { tree(); }*/ else { cout << dpp() << "\n"; } } return 0; } |