#include <bits/stdc++.h> using namespace std; int n, k, q; vector<int> v; vector<long long> val; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> q; v.resize(n); val.resize(n); for (int &i: v) cin >> i; val[0] = v[0]; for (int i = 1; i < k; ++i) val[i] = val[i - 1] + (long long)v[i]; for (int i = k; i < n; ++i) val[i] = val[i - 1] + (long long)v[i] - (long long)v[i - k]; vector<long long> dp(n, 0); for (int Q = 0; Q < q; ++Q) { int l, r; cin >> l >> r; --l; r -= l; --l; for (int i = k; i <= r; ++i) dp[i] = dp[i - 1] >= dp[i - k] + val[i + l] ? dp[i - 1] : dp[i - k] + val[i + l]; cout << dp[r] << '\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 31 32 33 | #include <bits/stdc++.h> using namespace std; int n, k, q; vector<int> v; vector<long long> val; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k >> q; v.resize(n); val.resize(n); for (int &i: v) cin >> i; val[0] = v[0]; for (int i = 1; i < k; ++i) val[i] = val[i - 1] + (long long)v[i]; for (int i = k; i < n; ++i) val[i] = val[i - 1] + (long long)v[i] - (long long)v[i - k]; vector<long long> dp(n, 0); for (int Q = 0; Q < q; ++Q) { int l, r; cin >> l >> r; --l; r -= l; --l; for (int i = k; i <= r; ++i) dp[i] = dp[i - 1] >= dp[i - k] + val[i + l] ? dp[i - 1] : dp[i - k] + val[i + l]; cout << dp[r] << '\n'; } } |