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
| # include <bits/stdc++.h> typedef long long int LL; using namespace std;
const int N = 2e5+7; //const int INF = (~(1<<31));
int read(){ int x=0,f=1;char ch = getchar(); while(ch<'0'||ch>'9') ch = getchar(); while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();} return x; } /*******************************************/
int a[N]; int n,k;
LL mx[N]; # define lowbit(x) (x&-x) void update(int i,LL v){ for(;i<=n;i+=lowbit(i)) mx[i]=max(mx[i],v); }
LL getMax(int i){ if(i<=0) return 0; LL ans = 0; for(;i;i-=lowbit(i)) ans = max(ans,mx[i]); return ans; }
int main(){//printf("%d\n",INF); int _; scanf("%d",&_); while(_--){memset(mx,0,sizeof(mx)); scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) a[i]=read();
LL ans = 0,tmp; for(int i=1;i<=n;i++){ tmp=a[i]+getMax(i-k-1); update(i,tmp); ans = max(ans,tmp); } printf("%d\n",ans); } return 0; }
|