In a mystical TimeLand, a person's health and wealth is measured in terms of…
- User
In a mystical TimeLand, a person's health and wealth is measured in terms of time(seconds) left. Suppose a person there has 24x60x60 = 86400 seconds left, then he would live for another 1 day. A person dies when his time left becomes 0. Some time-amount can be borrowed from other person, or time-banks. Some time-amount can also be lend to another person, or can be used to buy stuffs.
Our hero Mr X, is in critical condition, has very less time left.
Today's the inaugural day of a new time-bank. So they are giving away free time-amount worth 1000 years.
Bank released N slips, A[1], A[2], .... A[N]. Each slip has a time-amount(can be +ve as well as -ve).
A person can pick any number of slips(even none, or all of them, or some of them) out of the N slips. But bank introduced a restriction, they announced one more number K. Restriction is that, if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. It means there should be a difference of atleast K between the indices of slips picked.
Now slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction.
If you predict the maximum positive sum possible, then you win.
Mr X has asked for your help. Help him win the lottery, and make it quick! Input Format: First line of the test file contains single number T, the number of test cases to follow. Each test case consists of two lines.First line contains two numbers N and K , separated by a space. Second line contains the N numbers A[1], A[2] ..... A[N] separated by space.
Output Format: For every test case, output in a single line the maximum positive sum possible, that is output for the case.
Constraints: T ≤ 250 N ≤ 10000 -10^9 ≤ A[i] ≤ 10^9 0 ≤ K ≤ N-1
SAMPLE INPUT 2 10 1 1 2 -3 -5 4 6 -3 2 -1 2 10 2 1 2 -3 -5 4 6 -3 2 -1 2
SAMPLE OUTPUT 12 10
Explanation
1st Case: We can take slips { A[2]=2, A[6]=6, A[8]=2, A[10]=2 }, slips are atleast 1 indices apart this makes maximum sum, A[2]+A[6]+A[8]+A[10]=12
2nd Case: We can take slips { A[2]=2, A[6]=6, A[10]=2 }, slips are atleast 2 indices apart this makes maximum sum, A[2]+A[6]+A[10]=10
Assistant
We need to solve the problem: Given array A of N integers (can be negative). We can select a subset of indices such that if we pick index i, the next pick must have index >= i+K+1 (i.e., at least K+1 apart, since difference of at least K means indices difference > K? Let's read: "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. It means there should be a difference of atleast K between the indices of slips picked." The phrasing: "difference of atleast K" might be ambiguous: If K=1, then next slip is A[i+2], so indices differ by at least 2? Actually they say "atleast K" so difference >= K? But they gave i+K+1, so difference = K+1? Let's check sample: N=10 K=1. They pick indices 2,6,8,10. Indices differences: 2 to 6 diff=4 (>=1? yes; >=2? yes). But they also pick 6 and 8 diff=2, but with K=1, next allowed is i+K+1 = i+2, so from i=6, next index must be >=8. That matches diff=2. So indeed, the constraint is that chosen indices must be at least K+1 apart? Wait: They pick 8 and 10 diff=2, from 8 next allowed is 10 (8+2). So they pick consecutive indices with a gap of exactly 2. So the constraint is that the next index must be >= i+K+1, i.e., difference > K? Because if K=1, then difference must be >=2? Actually difference = j-i, if j >= i+K+1 then j-i >= K+1 > K. So they require difference > K, or at least K+1. But they say "atleast K" but then example with K=1 uses at least 2 difference. Let's double-check: "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. It means there should be a difference of atleast K between the indices of slips picked." Possibly they meant difference at least K+1? Or they misinterpret: if difference at least K, then next slip would be A[i+K]. But they wrote A[i+K+1], so it's K+1. So it's clear: indices chosen must be such that the difference between successive picks is at least K+1 (i.e., no two picks are within K indices). So constraint: we cannot pick two indices i<j such that j-i <= K. This is like we need to select a subset with no two elements within distance K. And we want to maximize sum of selected elements, but we want the maximum positive sum possible. They say "maximum positive sum possible". If all selections result in non-positive sum, maybe we can select none? "a person can pick any number of slips(even none, or all of them, or some of them)". So if all sums are negative or zero, the best is 0 (by picking none) which is positive? 0 is not positive? They say "maximum positive sum possible". So we need a positive sum. If it's impossible to get a positive sum (i.e., all subsets sum <=0), what then? The problem statement: "output the maximum positive sum possible". In sample, they gave positive sums. Usually in such DP, we consider that we can choose empty set giving sum 0, but 0 is not positive. So we need to output the maximum sum > 0. If no selection yields a positive sum, then perhaps output 0? Or maybe it never occurs? But given constraints, A[i] can be negative, and we can skip all, so if all numbers are negative, best sum is 0 but not positive, so maybe we need to output something else? Could be that they consider empty set not allowed? The problem says "maximum positive sum possible". This suggests we must pick at least one slip? It says "slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible". So we need positive sum, so we must pick at least one. If no such selection, maybe output 0? But they might guarantee that there is at least one positive? Not necessarily. So we should handle that. Usually in similar problems (like max sum with distance constraints) we allow empty set giving sum 0, and if all are negative, answer is 0 (or sometimes maximum negative). But they explicitly say "positive". So we need to compute maximum sum > 0. If none, output 0? Or maybe they expect 0? Let's see typical problem: "Maximum sum subsequence such that no two elements are within K distance" and we can skip. But they stress positive. Probably because they talk about time-amount, which you want to gain, but you could also borrow negative? Actually slip can be -ve, meaning you lose time. So you wouldn't pick negative slips unless you have to? But you can skip. So you would pick only positives? But you might need to skip some positives if they are too close to each other? But you could also pick negative if it allows you to pick more positives later? No, because you can just skip negative ones; they don't force you to pick anything. So the optimal subset under distance constraint that maximizes sum would never include a negative element because you could simply omit it and possibly pick other positive ones. However, there's a twist: if you skip a negative, you might be able to pick a later positive that is within K of the negative? But the constraint is only about picks; skipping doesn't matter. So you can always ignore negative numbers. But wait, there is a distance constraint: if you pick a positive at index i, you cannot pick another positive at index i+1 if K=0? Actually if K=0, then constraint: if you pick A[i], next must be A[i+1]? Because i+K+1 = i+1, so difference >=1? That means you can pick consecutive indices? Let's think: K=0 -> next slip can be A[i+1]? Actually i+K+1 = i+1, so you can pick index i+1? That would be distance 1. But they say difference at least K (0). So with K=0, you can pick any indices, even adjacent? Actually if K=0, then the constraint is at least 0 difference, meaning you can pick the same index? But you can't pick same index twice. So maybe K=0 means you can pick adjacent? Because if K=0, i+K+1 = i+1, so you can pick the immediate next. So you can pick any set, no restriction? Let's re-evaluate: "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]." That means after picking index i, the next eligible index is i+K+1, i.e., you must skip at least K indices between picks. So if K=0, i+K+1 = i+1, so you can pick the very next index. So constraint is that you cannot pick two indices that are too close? Actually you can pick i and i+1 because i+1 >= i+K+1? For K=0, i+K+1 = i+1, so i+1 is allowed. So you can pick consecutive indices. So the restriction is that you cannot pick indices that are less than K+1 apart? Let's formalize: Let chosen indices be i1 < i2 < ... < im. The condition must be: i_{j+1} >= i_j + K + 1. So difference i_{j+1} - i_j >= K+1. That is exactly the constraint. For K=0, diff >=1, so any strictly increasing indices are allowed (i.e., you can pick any subset with distinct indices). For K=1, diff >=2, so you cannot pick adjacent indices. So the constraint is: no two selected indices are within K (i.e., at most K-1 apart)? Actually diff >= K+1 means they are at least K+1 apart, meaning there must be at least K indices between them? So yes.
Thus the problem reduces to: Given an array A[1..N], select a subset of indices such that the distance between any two consecutive selected indices is at least K+1, maximizing the sum. Since we can skip negative numbers, the optimal solution would only consider positive numbers? But not necessarily: Could there be a scenario where picking a negative number allows you to skip a large negative later? Actually skipping is free. The decision to pick or not pick at an index only affects which future indices are available? The constraint only restricts picking indices too close; picking a negative might block a later positive? But you could also skip the negative and then pick the later positive if it's far enough from previous picks. So picking a negative would only reduce sum and also possibly block some future positives (since after picking the negative, you must skip the next K indices). So it's never beneficial to pick a negative. So the optimal set consists of only positive numbers. However, we must also consider that we may need to skip some positive numbers if they are too close to each other. That's a classic problem: maximum sum subsequence with no two elements within distance d (where d = K+1). Actually we want to maximize sum of selected elements subject to constraint that chosen indices are at least d apart (d=K+1). Since we only pick positives, we can treat negative numbers as 0 and never pick them. Then the problem becomes: choose a subset of indices with at least d apart to maximize sum of A[i] (where A[i]>0). This can be solved by DP: dp[i] = maximum sum we can get considering first i elements, with the constraint. Standard DP: dp[i] = max(dp[i-1], dp[i-d] + A[i]) if we consider picking i or not. But careful: dp[i] should be the maximum sum for prefix up to i (considering indices 1..i) with the constraint and possibly not selecting i. The recurrence: dp[i] = max(dp[i-1], (i-d >= 0 ? dp[i-d] : 0) + A[i]) for i>=1. This works because if we pick i, we cannot pick any of the previous d-1 indices, so the best prior sum is from i-d. Also dp[0]=0. Then answer is dp[N]. However, this DP automatically picks only positive values if beneficial, because if A[i] is negative, dp[i] will be dp[i-1] which is better. So it's fine. And dp[N] is maximum sum possible, which could be 0 if all negative. But the problem demands positive sum. So we need to ensure that if dp[N] <= 0, we might need to output something else? Let's see the problem statement: "slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction." It says "maximum positive sum possible". So if the maximum achievable sum is non-positive (i.e., <=0), then there is no positive sum possible. In that case, maybe we output 0? But 0 is not positive. Possibly they intend to output 0? Many similar problems ask for "maximum sum" and include empty set giving 0. The phrase "positive" may just be emphasizing that they want gain, but they might still accept 0. However, sample has positive sums. Let's test with negative numbers only: Suppose N=1, A=[-5], K any. What should be output? According to story, picking none gives 0, but that's not positive. But maybe they consider that you can borrow time (positive) and negative is losing time, so you wouldn't pick any negative; but they want maximum positive sum, so maybe answer is 0 if you can't get positive? The problem says "maximum positive sum possible". If it's impossible, maybe they output 0 (or maybe -1?). We need to infer from typical contest problem. Usually they would ask for "maximum sum" and include empty set as sum 0. But here they explicitly say positive. However, it's possible that the scenario ensures that total sum of all slips is huge (1000 years) so there will be positive. But constraints don't guarantee. Could be tricky: They say "Bank released N slips, A[1]... A[N]. Each slip has a time-amount(can be +ve as well as -ve)." and they give away free time-amount worth 1000 years. So the sum of all slips? But they are giving away free time amount, so overall sum might be positive? Not necessarily; some slips may be negative. But likely they want the maximum sum even if it's 0 (by not picking). I'd assume that if all numbers are negative, the answer should be 0? But 0 is not positive, but picking none yields 0, which is not positive sum? Actually it's zero sum. They ask for positive sum. So maybe we must output the maximum sum >0, and if none, output 0? Or maybe they expect 0. Let's check typical problem: "Given an array, find maximum sum of subsequence with no two elements adjacent" classic house robber. That yields non-negative answer (since you can skip all). If they ask for "maximum positive sum", they might want at least one element. But the sample: In first case, there are positive numbers. In second, also. So no clue.
We can try to see if there is any twist: The array values can be large up to 1e9, N up to 10000, T up to 250. So total N across tests could be up to 2.5e6? 250*10000 = 2.5 million, which is fine. The DP O(N) per test is acceptable. However, we need to handle K up to N-1. d = K+1 can be up to N. So DP using O(N) memory is fine.
But wait: The constraint says "0 ≤ K ≤ N-1". So d = K+1 can be as large as N. Then dp[i-d] may be negative index. So handle accordingly.
But let's double-check the recurrence: For i, if we pick A[i], we must ensure that previous pick is at most i-d. The best sum for prefix up to i-d (any configuration) is dp[i-d]. However, we also need to consider that we might have skipped some earlier ones; dp[i-d] is the maximum sum for prefix i-d (maybe last selected index is less than i-d, which is fine). So picking A[i] yields dp[i-d] + A[i]. If i-d < 0, treat dp[negative] = 0. Then dp[i] = max(dp[i-1], dp[i-d] + A[i]). This gives maximum sum with the constraint that we can pick any subset. This is standard for "maximum sum subsequence with at least K distance between chosen elements".
But there is nuance: The constraint says "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]." That means after picking i, you cannot pick any of the next K slips. But you could pick earlier slips? Order is increasing indices as you pick; you start from the smallest index you pick. So effectively, for any two picks i<j, we need j-i >= K+1. This matches the constraint.
Thus DP works.
However, is there any possibility of picking slips in non-increasing order? Usually you pick in increasing order of indices because you go through slips sequentially. So it's fine.
Now, what about the requirement "maximum positive sum possible"? The DP will produce maximum sum, which could be zero or negative if all A[i] are negative. But if all are negative, dp[N] will be 0 (since we can pick none). Actually dp[i] = max(dp[i-1], dp[i-d] + A[i]) with dp[0]=0. If all A[i] < 0, then dp[i] will stay 0 because picking negative yields less than 0, and dp[i-1] is 0. So dp[N] = 0. That's not positive. So we need to output something else. Possibly they require at least one slip to be picked, so we cannot pick none. If we must pick at least one, then the answer would be the maximum element (since we can pick just one). That would be negative if all are negative, so maybe answer negative? But they say "positive sum". So maybe the scenario ensures there is at least one positive? Not necessarily but maybe the free time-amount worth 1000 years implies overall sum of slips is positive, but individual may be negative. But it's not guaranteed that any single slip is positive. Actually they are giving away free time-amount worth 1000 years; that could mean that the sum of all slips is 1000 years? Or maybe each slip is from that pool? The description: "Bank released N slips, A[1], A[2], .... A[N]. Each slip has a time-amount(can be +ve as well as -ve)." and "they are giving away free time-amount worth 1000 years." Could be that the sum of all slips is 1000 years? Or maybe they give away 1000 years separately? Not clear.
Given typical competitive programming problems, they usually ask for "maximum sum" and empty set yields 0. The addition of "positive" might be just narrative. I'd check the sample: For first test case, they got 12. If we compute DP with d = K+1 = 2: Let's compute: N=10, K=1, d=2. A = [1,2,-3,-5,4,6,-3,2,-1,2]. DP: dp[0]=0. i=1: dp[1] = max(dp[0], dp[-1?] + A[1]) = max(0, 0+1)=1. i=2: dp[2] = max(dp[1]=1, dp[0]+A[2]=0+2=2) =2. i=3: dp[3] = max(dp[2]=2, dp[1]+A[3]=1+(-3)=-2) =2. i=4: dp[4] = max(dp[3]=2, dp[2]+A[4]=2+(-5)=-3) =2. i=5: dp[5] = max(dp[4]=2, dp[3]+A[5]=2+4=6) =6. i=6: dp[6] = max(dp[5]=6, dp[4]+A[6]=2+6=8) =8? Wait dp[4]=2, so 2+6=8, so dp[6]=max(6,8)=8. i=7: dp[7] = max(dp[6]=8, dp[5]+A[7]=6+(-3)=3) =8. i=8: dp[8] = max(dp[7]=8, dp[6]+A[8]=8+2=10) =10. i=9: dp[9] = max(dp[8]=10, dp[7]+A[9]=8+(-1)=7) =10. i=10: dp[10] = max(dp[9]=10, dp[8]+A[10]=10+2=12) =12. So dp[10]=12 matches sample.
Second test: K=2, d=3. DP: dp[0]=0. i=1: max(0, dp[-2]+1)=1 => dp1=1 i=2: max(dp1=1, dp[-1]+2=2) =>2 i=3: max(dp2=2, dp0+(-3)= -3) =>2 i=4: max(dp3=2, dp1+(-5)=1-5=-4) =>2 i=5: max(dp4=2, dp2+4=2+4=6) =>6 i=6: max(dp5=6, dp3+6=2+6=8) =>8 i=7: max(dp6=8, dp4+(-3)=2-3=-1) =>8 i=8: max(dp7=8, dp5+2=6+2=8) =>8 (or 8) i=9: max(dp8=8, dp6+(-1)=8-1=7) =>8 i=10: max(dp9=8, dp7+2=8+2=10) =>10 Matches sample.
Thus DP works. So answer is dp[N] (which could be 0). But they say "maximum positive sum possible". dp[N] is maximum sum (including empty set 0). If all numbers are negative, dp[N] = 0. Is 0 considered positive? No. So perhaps they want the maximum sum that is >0; if dp[N] <= 0, maybe we need to output 0 or maybe something else. I think it's safe to output dp[N] as the answer. Because in many problems they don't strictly enforce positivity and still say positive. Let's read problem statement: "slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction." They want the maximum positive sum, i.e., among all sums that are positive, we need the maximum. If no sum is positive, there is no answer? But they'd likely output 0. Alternatively, they might intend that you must pick at least one slip. However, the sample doesn't resolve. Let's check if picking no slip is allowed: They said "any number of slips (even none, or all of them, or some of them)". So picking none is allowed. So sum=0 is possible. But is 0 considered positive? No. So the set of positive sums might be empty if all sums from non-empty selections are <=0. Then the maximum positive sum does not exist. But in programming contest, they'd probably say if no such selection, output 0. Or they'd ask for maximum sum (which could be 0). Possibly the phrase "positive" is just to emphasize that you want to gain time; but they don't forbid zero. I'd output dp[N] as the answer. Since dp[N] is the maximum possible sum (including empty set). Usually they'd not have negative answer because you can always skip all and get 0. So it's okay.
Now we need to consider large T (250) and N up to 10000, which is fine. But we need to be careful about using 64-bit integers (long long) because sums can be up to N * 1e9 = 1e13, fits in 64-bit (9e12) Actually N=10000, max positive each 1e9, sum up to 1e13, which fits in 64-bit (9.22e18). So use long long.
Now the DP described is O(N) per test, using O(N) memory. But we can reduce memory to O(d) if we want, but N is only 10000, so O(N) is fine for T=250 => max total N = 2.5e6, dp array of size 10000 per test, that's 2.5e6 * 8 = 20 MB, which is fine. However, T is up to 250, but N is not always 10000; average might be lower. So memory okay.
But we need to ensure we don't have stack overflow if we allocate array per test. In C++, we can allocate vector per test.
Edge Cases: K can be large, e.g., K = N-1, then d = N. Then dp[i] = max(dp[i-1], (i-d >=0? dp[i-d]:0)+A[i]) but i-d will be negative for i < d, so we treat as 0. Effectively we can only pick at most one element (since picking one blocks all others). The DP will correctly compute maximum of 0 and each A[i] (since dp[i] = max(dp[i-1], A[i])? Actually if d=N, then for i from 1 to N: dp[i] = max(dp[i-1], A[i])? Not exactly: dp[i-d] is 0 for i<d, and dp[0]=0. So dp[i] = max(dp[i-1], A[i]) for i <= N? But also if i >= d, i-d = i-N, which is 0? Actually if i=N, i-d=0, dp[0]=0, so dp[N]=max(dp[N-1], A[N]) which is max of all A's. But is that correct? Because if we pick one element at i, we cannot pick any other because they are all within distance < N? Actually if K=N-1, then d=N. Constraint: difference >= N, so if we pick one element, next must be at index at least i+N. Since N is total length, only one can be picked. So maximum sum is max(0, max_i A[i]). Yes, DP gives that.
Now, we need to ensure that the DP correctly handles negative A[i] and ensures we never pick a negative if it reduces sum. It does because max with dp[i-1] will keep the non-negative sum.
Thus solution is straightforward.
But wait: Is there any trick about the order? The bank releases slips and you can pick any number, but restriction is that if you pick a slip A[i], then the next slip that you can choose to pick will be A[i+K+1]. That means you can only pick in increasing index order? Yes. Also you can start with any slip. So DP works.
Thus we can implement.
But let's consider an alternative: The DP recurrence might need to consider that when you pick A[i], you cannot pick any from i-K to i-1? Actually the constraint is that after picking i, the next pick must be at least i+K+1. So you cannot pick any index j such that j < i? Actually picks are in increasing order. So if you pick i, you cannot pick any j where j > i and j-i <= K. So it's forward restriction. For DP, we ensure that if we pick i, the previous pick must be at most i-K-1. So yes.
Thus solution is DP.
Now, is there any need to consider that K can be zero? Then d=1. Then dp[i] = max(dp[i-1], dp[i-1] + A[i])? Wait if d=1, then i-d = i-1. So recurrence: dp[i] = max(dp[i-1], dp[i-1] + A[i]). That's dp[i] = dp[i-1] + max(0, A[i])? Actually dp[i] = max(dp[i-1], dp[i-1] + A[i]) = dp[i-1] + max(0, A[i])? Not exactly: If A[i] is positive, dp[i] = dp[i-1] + A[i] (since that's larger). If A[i] negative, dp[i] = dp[i-1]. So this means we pick all positive numbers! Because with K=0, there's no restriction? Wait, with K=0, constraint says next pick must be at least i+1, meaning we can pick adjacent indices. So we can pick all indices. So maximum sum would be sum of all positive numbers (since we can skip negatives). So DP yields dp[i] = dp[i-1] + A[i] if A[i]>0 else dp[i-1]. That's sum of all positives. That's correct.
Thus DP works for all K.
Now, we must be careful about indexing: Use 1-indexed array for simplicity. dp[0] = 0. For i from 1 to N: dp[i] = max(dp[i-1], (i - (K+1) >= 0 ? dp[i - (K+1)] : 0) + A[i]). That's it.
But note: The constraint says "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]." So if you pick i, you can only pick next from i+K+1 onward. That means the gap is at least K+1. So d = K+1. Good.
Thus solution is straightforward.
Now we also need to consider that maybe we can pick slips in any order, but we can also skip many. The DP covers that.
Now the problem statement: "Now slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction." They emphasize "positive". I'd like to test a case: N=1, A=[-5], K=0. dp[1] = max(dp[0]=0, dp[0]+(-5) = -5) = 0. So answer 0. Is 0 considered positive? No. But maybe the problem expects 0 anyway. The problem might be from some contest where they want "maximum sum" and they print 0 if all are negative. I'd output dp[N] as is. If dp[N] <= 0, output 0. That would be consistent with "maximum positive sum" but if none, output 0. Or maybe they'd output "0" as well, because they might treat 0 as not positive but still the best possible. Usually they'd ask "maximum non-negative sum" if they want 0. But they said positive, so maybe it's guaranteed there is at least one positive A[i]? Not necessarily, but maybe input guarantees that the total free time-amount worth 1000 years means that the sum of all A[i] equals 1000 years? But 1000 years in seconds? That would be huge. Or perhaps the free time-amount is distributed across slips. Not clear. But we can be safe: we will output dp[N], which is the maximum sum achievable (including empty set). Since the problem says "maximum positive sum possible", if dp[N] = 0, then it's not positive, but perhaps they accept 0. I'll assume it's correct.
But let's double-check sample: they output 12 and 10. So dp[N] works.
Now, we should consider potential pitfalls: The DP might overflow if we use int. Use long long. Also K and N up to 10000, K+1 could be up to 10000, so dp array size N+1 is fine.
Complexity: O(N) per test.
Now, let's think if there is any nuance about the distance being at least K or at least K+1? Sample confirmed K+1. For K=1 they picked indices with difference 2, so d=2 = K+1. So correct.
Now, one more nuance: The DP recurrence uses dp[i-d] where d = K+1. But what if K is large, say K = 5 and we have i=3, i-d = negative, we treat as 0. That's fine.
Now, also need to ensure that the DP's choice of picking A[i] does not conflict with the possibility of picking later indices; but DP builds optimal for prefix, so it's correct.
Now, what about alternative solution with O(N) sliding window? Not needed.
Thus solution: For each test case, read N, K. Read array A (size N). Compute d = K+1. Initialize dp of size N+1, dp[0]=0. For i from 1 to N: pick = A[i-1] + (i-d >= 0 ? dp[i-d] : 0); dp[i] = max(dp[i-1], pick); Then print dp[N].
But careful: If we use 0-indexed A, i corresponds to index i (1-indexed). So A[i-1] is the element. So code: pick = A[i-1] + (i-d >= 0 ? dp[i-d] : 0); dp[i] = max(dp[i-1], pick);
Now, we must use 64-bit for dp and pick. dp[i] can be up to 1e13, fits in long long.
But wait: A[i] can be -1e9, so pick could be negative. dp[i] will be at least dp[i-1] which is >=0, so dp[i] stays non-negative. So dp is non-decreasing? Not necessarily, because dp[i-1] can be same or increase. But it never decreases. So dp[N] is non-negative.
Now, is there any scenario where dp[i] becomes negative? Since we have base 0, and max with dp[i-1] which is non-negative, dp[i] is always >=0. So answer is non-negative.
Now, the problem statement might have additional nuance: "maximum positive sum possible" could also imply that we need to pick at least one slip. If we must pick at least one, then answer could be negative if all numbers are negative. But then it wouldn't be positive. So maybe they guarantee that it's possible to get a positive sum, because the bank is giving away free time. So I'd assume dp[N] > 0. But still we can handle.
Now, consider T up to 250 and N up to 10000, so total input size could be up to 2.5e6 numbers, which is okay.
Now, we can also optimize memory by using a single array or two variables, but not needed.
But we should consider that N=10000, but K could be 0, then d=1, dp[i] only depends on dp[i-1] and dp[i-1] (since i-d = i-1). So we could compute in O(1) memory, but it's fine.
Now, I'll produce solution in C++.
Potential pitfalls: Input may be large, so use fast IO (cin with sync_with_stdio(false), or scanf). We'll use scanf.
Edge Cases: K can be larger than N, but constraints say K ≤ N-1, so K+1 ≤ N, so d ≤ N. So when i-d negative only for i<d.
Now, the DP we used is standard.
But wait: Is it always optimal to consider only dp[i-d] when picking i? Could there be a scenario where we pick i and the previous pick is at index < i-d, but we might also consider that we could have a configuration that does not use dp[i-d] exactly but something else? Since dp[i-d] is the maximum sum for prefix up to i-d, it is optimal; any valid configuration that ends with a pick at i must have the previous pick at most i-d (since difference >= d). The best sum for such a configuration is dp[i-d] + A[i] because dp[i-d] already accounts for the best sum for indices up to i-d, and we don't need to worry about whether the last pick in that configuration is exactly i-d or earlier; it's allowed because if the last pick is earlier than i-d, then there is a gap of more than d, which is fine. So dp[i-d] works.
Thus DP is correct.
Now, is there any nuance about the order of picking? The bank restriction says "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]." It doesn't say you cannot pick a slip before you pick the previous one? Obviously you pick in increasing order. So DP covers.
Now, implement.
But note: Some may think that the DP recurrence might need to consider that you can skip some indices and then pick, which is covered.
Thus answer is straightforward.
Now, I'll craft the final solution.
However, there is another perspective: This is essentially a variant of the classic "Maximum sum of non-adjacent elements" for K=1 (adjacent not allowed). For general K, it's "at least K apart".
We can also solve using a segment tree or something for large N, but N is small.
One more nuance: The DP as described runs O(N). But careful: The recurrence uses dp[i-d] which may be up to 10000 earlier. So O(1) per step.
Now, to be thorough, let's test with some random small cases with brute force to confirm.
Case: N=3, A=[-1,-2,-3], K=0. DP: d=1. i1: pick = -1+0=-1, dp1=max(0,-1)=0. i2: pick = -2+dp1= -2, dp2=max(0,-2)=0. i3: pick = -3+dp2= -3, dp3=max(0,-3)=0. Answer 0. Brute: best is not pick any, sum=0. Positive sums not possible. So output 0.
Case: N=3, A=[-1,5,-2], K=1 (d=2). DP: i1: pick = -1+0=-1, dp1=max(0,-1)=0. i2: pick = 5+0=5, dp2=max(0,5)=5. i3: pick = -2+dp1 = -2+0=-2, dp3 = max(dp2=5, -2) =5. Answer 5. Brute: cannot pick 1 and 2 (distance 1 <2) so best is pick 2 only ->5. Or pick 1 and 3? 1 and 3 distance 2 -> allowed, sum = -1 + -2 = -3, not good. So answer 5.
Case: N=5, A=[1,2,3,4,5], K=2 (d=3). DP: i1: pick=1+0=1 dp1=1 i2: pick=2+0=2 dp2=max(1,2)=2 i3: pick=3+0=3 dp3=max(2,3)=3 i4: pick=4+dp1=4+1=5 dp4=max(3,5)=5 i5: pick=5+dp2=5+2=7 dp5=max(5,7)=7. So answer 7 (pick indices 2 and 5? Actually 2 and 5 diff=3? 5-2=3 >=3, allowed: sum=2+5=7; or 1 and 4: 1+4=5; or 3 only:3; so 7 correct.
Now, what about case where picking a negative could allow a later larger positive? Example: A = [5, -1, -1, 5], K=1 (d=2). If we pick index1=5, then cannot pick index2 or 3, but can pick index4? Distance from 1 to 4 =3 >=2, so allowed. So sum=5+5=10. But if we skip index1, we could pick index2=-1 and index4=5? But we wouldn't pick -1. Could also pick index2 and index4? index2=-1, index4 allowed? diff=2, allowed. Sum=4. So best is 10. DP: i1: pick=5, dp1=5; i2: pick= -1+0=-1, dp2=max(5,-1)=5; i3: pick=-1+dp1? Wait i3: pick = A[3]? Actually indices: 1:5, 2:-1, 3:-1, 4:5. d=2. i1: pick=5, dp1=5. i2: pick = -1 + (i-d>=0? dp[0]=0) = -1, dp2 = max(5,-1)=5. i3: pick = -1 + dp[1]? i=3, i-d=1, dp1=5, so pick = -1+5=4, dp3 = max(dp2=5, 4)=5. i4: pick = 5 + dp[2]? i-d=2, dp2=5, so pick = 5+5=10, dp4 = max(dp3=5,10)=10. So DP yields 10. Good.
Now, if we have a negative that enables better later? Actually picking a negative is never beneficial because you can always skip it and still pick later positives as long as they are not blocked by skipping? But skipping a negative may actually allow picking more positives? For example, if we have positives that are close together, we may need to skip some positives to adhere to distance constraint. But picking a negative would block some positions and might reduce sum. So DP automatically picks optimal.
Thus solution stands.
Now we need to write code. Use scanf for speed.
Pseudo:
int T; scanf("%d", &T); while(T--) { int N, K; scanf("%d%d", &N, &K); vector A(N); for(int i=0; i<N; i++) { scanf("%lld", &A[i]); // Actually A[i] can be up to 1e9, fits in int, but use long long for safety. } int d = K+1; vector dp(N+1, 0); for(int i=1; i<=N; i++) { long long take = A[i-1] + (i-d >= 0 ? dp[i-d] : 0); dp[i] = max(dp[i-1], take); } printf("%lld\n", dp[N]); }
But note that A[i] might be negative, and take may be negative, but dp[i] is max with previous dp which is non-negative, so dp[i] stays non-negative.
Now, I'm thinking about potential integer overflow: A[i] up to 1e9, dp up to 1e13, so within 64-bit.
Now, we could also use a rolling array to save memory but not needed.
Now, test with sample.
Now, one more nuance: The input says A[i] can be negative and up to 1e9 in absolute value. So reading as int is fine but we should store in long long to avoid overflow in sums. But scanf("%d") for int then cast to long long is okay. But we can read as long long to be safe.
Now, about output: Should be long long.
Edge Cases: K=0, d=1, DP works.
Now, is there any possibility that we need to consider picking slips in any order? Actually you might pick slips in any order but you cannot pick a slip after you have already picked one that is too close. The DP assumes increasing order, but you could pick in decreasing order? No, order of picking presumably follows the order you pick them; you can start with any slip, then the next must have higher index? The statement: "if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]." This implies that after picking i, the next slip you can pick is at index i+K+1, which is greater than i. So you only go forward. So ordering is increasing.
Thus solution is correct.
Now, I'll produce final answer with explanation.
But before finalizing, I'll double-check the DP for a scenario where d > i. When i-d < 0, we treat dp[negative] = 0, which means we can pick i as first element. That's correct.
Now, what about if K is large such that d > N? Actually d can be up to N, but i-d negative for all i < d, and for i = d, i-d = 0, we have dp[0]=0. So fine.
Now, complexity: O(T*N). With T=250, N=10000, it's 2.5e6 operations, very fast.
Now, there might be a trick: The problem might require modulo? No.
Now, we can also implement with O(N) memory but could also implement O(d) memory if needed but not.
Now, I'll craft final solution.
But wait, there is a nuance: The DP as described picks elements such that they are at least d apart. However, does it correctly handle the case where we pick multiple elements? Yes.
We can also think of a variant: maybe you can skip slips arbitrarily, but the restriction only applies to picks: after picking i, the next pick must be at least i+K+1, but you could also pick slips before i? Not after you picked i, you cannot go back. So DP works.
Thus final answer.
Now, we should write explanation for the solution.
Let's write:
We define d = K+1 as the minimum gap between selected indices.
We want maximum sum of selected numbers under constraint that chosen indices i1 < i2 < ... < im satisfy i_{j+1} - i_j >= d.
We can use DP: dp[i] = maximum sum we can obtain considering first i elements (A[1..i]). For each i, we have two options: either we do not select A[i], then dp[i] = dp[i-1]; or we select A[i], then we cannot select any of the previous d-1 elements, so the best we can add is dp[i-d] + A[i] (where dp[0]=0). So dp[i] = max(dp[i-1], dp[i-d] + A[i]).
Finally answer is dp[N].
Since we can choose no slips, dp[i] is always >= 0. If all numbers are negative, answer 0, which is the maximum non-positive sum? The problem asks for maximum positive sum but if no positive sum exists, 0 is likely acceptable.
Complexities: O(N) time per test, O(N) memory (or O(1) with rolling).
Implementation details: Use 64-bit integers.
Now, we can also reduce memory by using a circular buffer of size d, but not necessary.
Now, produce final code.
But I'll also handle large input with fast I/O.
Potential pitfalls: The dp array can be of size N+1, and for each test we allocate. Since T up to 250 and N up to 10000, total memory allocation might be high if we allocate separately, but it's okay because each allocation freed after test.
Now, test with sample:
Input: 2 10 1 1 2 -3 -5 4 6 -3 2 -1 2 10 2 1 2 -3 -5 4 6 -3 2 -1 2
Our code would output: 12 10
Matches.
Now, I will write solution in C++.
Also note: I should use "%lld" for long long in printf/scanf? Actually on many platforms, long long uses %lld. But to be safe, I can use 'long long' and with cin/cout? But for speed, scanf/printf.
However, using cin with ios_base::sync_with_stdio(false) and cin.tie(NULL) is also fast enough for 2.5e6 numbers. Let's compute: 2.5e6 numbers * reading per number ~ a few ms. So cin is fine. But to be safe, we can use scanf.
I'll implement with scanf.
Now, final code:
#include <bits/stdc++.h> using namespace std;
int main() { int T; scanf("%d", &T); while (T--) { int N, K; scanf("%d %d", &N, &K); vector A(N); for (int i = 0; i < N; ++i) { scanf("%lld", &A[i]); } int d = K + 1; vector dp(N + 1, 0); for (int i = 1; i <= N; ++i) { long long take = A[i-1] + (i - d >= 0 ? dp[i - d] : 0); dp[i] = max(dp[i-1], take); } printf("%lld\n", dp[N]); } return 0; }
But wait, A[i] is int range, but we use %lld. That's fine because we read into long long variable. However, scanf expects pointer to long long, which is okay. Alternatively, we can read as int and assign.
Now, test with negative numbers: N=1, A=[-5], K=0 => dp[1]=max(0, -5)=0 output 0.
Now, is there any situation where dp[i] could be negative? Only if all dp[i-1] were negative and take is also negative, but dp[0]=0 ensures dp[i] >= 0. So dp is non-negative.
Now, if we need to output the maximum positive sum, and dp[N] = 0, that's not positive. But maybe the problem expects 0. Let's see if there is any note about "positive". Possibly they want to output 0 if no positive sum. But we can't be sure. I'd keep as is.
But maybe there is a twist: The bank gives free time amount worth 1000 years. Could be that the sum of all slips is 1000 years? But not necessarily. Not needed.
Thus answer.
Now, I'll also think about alternative approach: This DP is essentially like "Maximum sum of subsequence with at least K distance between consecutive picks". It's a standard DP.
Now, before finalizing, let's check a corner case: K = N-1, d = N. DP: for i=1..N: i=1: take = A[0] + 0, dp1 = max(0, A0) i=2: take = A1 + 0, dp2 = max(dp1, A1) ... So dpN = max(0, max_i A[i]) correct.
Now, consider K large but less than N. For i < d, dp[i] = max(dp[i-1], A[i-1]), because i-d negative => take = A[i-1]. So for first d-1 elements, dp[i] is the max of previous dp (which is max of previous A's) and current A. So dp[i] = max(max(A[0..i-1]), A[i-1])? Actually it's just the running maximum. That's correct because you can pick at most one among first d elements (since any two would be within d). So you choose the best single element (or none).
Now, final solution is done.
But there is a nuance: In the DP, when we pick A[i], we add dp[i-d]. However, what if dp[i-d] corresponds to a configuration where the last picked index is exactly i-d? Then the distance between that last pick and i is exactly d, which is allowed because d = K+1 >= K+1? Actually we need difference >= K+1, so exactly d is allowed. So fine.
Now, I will produce the final answer.
But the problem might require reading T up to 250, and N up to 10000. Could there be a need for more optimized approach? O(N) per test is fine.
Now, let's consider a possible improvement: we can use a variable to store the maximum dp among those indices that are at least d behind, but we already have dp array, so O(1) per i anyway.
Thus we are done.
Now, I will write the final answer with explanation.
Potential pitfalls: Using int for dp might overflow, so long long is must.
Now, I will produce final message. The problem reduces to selecting a subset of indices with the constraint that the difference between any two consecutive chosen indices is at least K+1, and maximizing the sum of the selected numbers. Since negative numbers are never beneficial (they only reduce the sum and block later picks), the optimal solution consists only of positive numbers, but the DP automatically handles negatives by skipping them.
Let
d = K + 1. For each prefixi(1‑based), definedp[i]as the maximum achievable sum using elements fromA[1..i]while respecting the distance constraint. Two options exist for the element at positioni:- Do not pick it: the answer is
dp[i-1]. - Pick it: then the previous chosen index must be at most
i - d. The best sum we can have from the firsti-delements isdp[i-d](withdp[0] = 0), so the total becomesdp[i-d] + A[i].
Thus
dp[i] = max(dp[i-1], dp[i-d] + A[i]).The final answer is
dp[N]. This value is always non‑negative because we can always choose no slips (sum = 0).The algorithm runs in O(N) time per test case, with O(N) memory (which can be reduced to O(d) if needed). Given the constraints (
T ≤ 250,N ≤ 10000), this is efficient.#include <bits/stdc++.h> using namespace std; int main() { int T; scanf("%d", &T); while (T--) { int N, K; scanf("%d %d", &N, &K); vector<long long> A(N); for (int i = 0; i < N; ++i) scanf("%lld", &A[i]); int d = K + 1; vector<long long> dp(N + 1, 0); for (int i = 1; i <= N; ++i) { long long take = A[i-1] + (i - d >= 0 ? dp[i-d] : 0); dp[i] = max(dp[i-1], take); } printf("%lld\n", dp[N]); } return 0; }- Do not pick it: the answer is