#include <bits/stdc++.h> using namespace std; typedef long long ll; struct odc{ int a; int b; int indx; }; bool acompare(odc l, odc p) { if (l.a<p.a) return true; else if (l.a==p.a){ return l.b>p.b; }else return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int n,k,q; cin>>n>>k>>q; int a,b; vector <ll> pref(n+1,0); //przerobić na globalną !! vector <ll> dp(n+1,0); vector <odc> zap; vector <ll> wyn(q,0); //Wczytywanie sily i liczenie pref for (int i=1;i<=n;i++){ cin>>a; pref[i]=pref[i-1]+a; } //Wczytwanie zapytan for (int j=0;j<q;j++){ cin>>a>>b; zap.push_back({a,b,j}); } //sortowanie zapytan po a,b sort(zap.begin(), zap.end(), acompare); // for (auto e:zap){ // cout<<e.a<<" "<<e.b<<" "<<e.indx<<endl; // } ll roz=0; // int kon=0,pocz=0; // odc o; int poprz_a=0; int poprz_b=0; int ind; for (int j=0;j<q;j++){ auto [a,b,ind]=zap[j]; if(b-a<k-1){ // wyn[zap[j].indx]=0; //nie trzeba bo 0 juz sa continue; } //nie tezeba liczyć jeśli pocz prze taki sam if (a!=poprz_a){ //zerowanie od a-1,a+k-1 // cout<<(a-1)<<" "<<b-k<<" "<<a+k-1<<endl; // fill(dp.begin() + (a-1),dp.begin()+b-k, 0); // pocz=max(a-1,kon); // kon=min(a+k-1,b-k); // cout<<"Zerowanie od "<<a-1<<" do "<<kon<<endl; // for (int p=pocz;p<=kon;p++){ // dp[p]=0; // // cout<<"zeruje"<<p<<endl; // } dp[a+k-1-1]=0; for (int i=a+k-1;i<=b;i++){ roz=pref[i]-pref[i-k]; if (i-k<(a+k-1)){ dp[i]=max(roz,dp[i-1]); } else dp[i]=max(dp[i-k]+roz,dp[i-1]); } } wyn[zap[j].indx]=dp[b]; poprz_a=a; poprz_b=b; } for (auto e:wyn){ cout<<e<<"\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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | #include <bits/stdc++.h> using namespace std; typedef long long ll; struct odc{ int a; int b; int indx; }; bool acompare(odc l, odc p) { if (l.a<p.a) return true; else if (l.a==p.a){ return l.b>p.b; }else return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int n,k,q; cin>>n>>k>>q; int a,b; vector <ll> pref(n+1,0); //przerobić na globalną !! vector <ll> dp(n+1,0); vector <odc> zap; vector <ll> wyn(q,0); //Wczytywanie sily i liczenie pref for (int i=1;i<=n;i++){ cin>>a; pref[i]=pref[i-1]+a; } //Wczytwanie zapytan for (int j=0;j<q;j++){ cin>>a>>b; zap.push_back({a,b,j}); } //sortowanie zapytan po a,b sort(zap.begin(), zap.end(), acompare); // for (auto e:zap){ // cout<<e.a<<" "<<e.b<<" "<<e.indx<<endl; // } ll roz=0; // int kon=0,pocz=0; // odc o; int poprz_a=0; int poprz_b=0; int ind; for (int j=0;j<q;j++){ auto [a,b,ind]=zap[j]; if(b-a<k-1){ // wyn[zap[j].indx]=0; //nie trzeba bo 0 juz sa continue; } //nie tezeba liczyć jeśli pocz prze taki sam if (a!=poprz_a){ //zerowanie od a-1,a+k-1 // cout<<(a-1)<<" "<<b-k<<" "<<a+k-1<<endl; // fill(dp.begin() + (a-1),dp.begin()+b-k, 0); // pocz=max(a-1,kon); // kon=min(a+k-1,b-k); // cout<<"Zerowanie od "<<a-1<<" do "<<kon<<endl; // for (int p=pocz;p<=kon;p++){ // dp[p]=0; // // cout<<"zeruje"<<p<<endl; // } dp[a+k-1-1]=0; for (int i=a+k-1;i<=b;i++){ roz=pref[i]-pref[i-k]; if (i-k<(a+k-1)){ dp[i]=max(roz,dp[i-1]); } else dp[i]=max(dp[i-k]+roz,dp[i-1]); } } wyn[zap[j].indx]=dp[b]; poprz_a=a; poprz_b=b; } for (auto e:wyn){ cout<<e<<"\n"; } return 0; } |