#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5+5; ll tab[N]; ll dp[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,k,q,a,b; cin >> n >> k >> q; for(int i=1; i<=n; ++i){ cin >> tab[i]; } while(q--){ cin >> a >> b; dp[0] = 0; for(int i=a,ii=1; i<=b; ++i,++ii){ dp[ii] = dp[ii-1]; if(ii>=k){ ll val = dp[ii-k]; for(int x=0; x<k; ++x){ val += tab[i-x]; } dp[ii] = max(dp[ii],val); } } cout << dp[b-a+1] << '\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 | #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5+5; ll tab[N]; ll dp[N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,k,q,a,b; cin >> n >> k >> q; for(int i=1; i<=n; ++i){ cin >> tab[i]; } while(q--){ cin >> a >> b; dp[0] = 0; for(int i=a,ii=1; i<=b; ++i,++ii){ dp[ii] = dp[ii-1]; if(ii>=k){ ll val = dp[ii-k]; for(int x=0; x<k; ++x){ val += tab[i-x]; } dp[ii] = max(dp[ii],val); } } cout << dp[b-a+1] << '\n'; } return 0; } |