#include <iostream> #include <vector> using namespace std; typedef long long LL; int main() { cin.tie(0); ios_base::sync_with_stdio(0); int n, k, q; cin >> n >> k >> q; vector <int> v(n); for (auto& x : v) cin >> x; while (q--) { int l, r; cin >> l >> r; l--; r--; if (r - l + 1 < k) { cout << 0 << "\n"; continue; } long long sum = 0; vector <long long> dp(r - l+1); for (int i = l; i < l + k; i++) sum += v[i]; dp[k-1] =sum; for (int i = k; i <= r - l; i++) { sum -= v[i - k + l]; sum += v[i + l]; dp[i] = max(max (0LL, dp[i - 1]), sum + max(0LL, dp[i - k])); } cout << max(0LL, dp.back()) << "\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 34 35 36 37 38 39 40 41 | #include <iostream> #include <vector> using namespace std; typedef long long LL; int main() { cin.tie(0); ios_base::sync_with_stdio(0); int n, k, q; cin >> n >> k >> q; vector <int> v(n); for (auto& x : v) cin >> x; while (q--) { int l, r; cin >> l >> r; l--; r--; if (r - l + 1 < k) { cout << 0 << "\n"; continue; } long long sum = 0; vector <long long> dp(r - l+1); for (int i = l; i < l + k; i++) sum += v[i]; dp[k-1] =sum; for (int i = k; i <= r - l; i++) { sum -= v[i - k + l]; sum += v[i + l]; dp[i] = max(max (0LL, dp[i - 1]), sum + max(0LL, dp[i - k])); } cout << max(0LL, dp.back()) << "\n"; } } |