My solution for D:
let's take first x elements from left and last y elements from right(x+y <=k and x<n-y+1).
we will look at negative elements in increasing order and if we have any operations left we'll put that negative element to it's own place.

my solution was dp and I think It could be solved with another ways but here's my explanation for my solution :

and state is dp[l][r][x] where l is the element we point at it in left , and r the element we point at it in r and x is number of remaining operations

every time we have 5 choices :

1 — pick element at l (decrease number of operations with 1) and add arr[l] to ans

2 — pick element at r (decrease number of operations with 1) and add arr[r] to ans

3 — pick element at l and leave it at end (decrease number of operations by 2)

4 — pick element at r and leave it at end (decrease number of operations by 2)

5 — don't pick or leave anything and answer for this choice is 0

dp[l][r][x] will be maximum of all this choices.

and here's my code : https://atcoder.jp/contests/abc128/submissions/5643132

Let C=A-B, iterate over all A. For a particular A we need C should divide n-1-A so try all possible divisors. For summing a particular pair A,C we need sum at gaps of C starting at 0 and A. To do fast sums observe C | n-1-A => A mod C = (n-1) mod C so for each C you need to store two cumulative sum vector (having starting position 0 and (n-1) mod C) at gap's of C which can be done in n log n.

Code for details : https://atcoder.jp/contests/abc128/submissions/5648719

For any $$$A$$$ and $$$B$$$ which reach $$$N - 1$$$, there is some $$$k$$$ such that $$$kA - (k - 1)B = N - 1$$$. Since $$$(k - 1)(A - B) < N$$$, we can iterate over all possible choices for $$$A - B$$$ and $$$k$$$ in $$$O(N log N)$$$.

For any choice of $$$A - B$$$ and $$$k$$$, we visit the spots $$$0, A - B, 2(A - B), \dots (k-1)(A - B)$$$ and the spots $$$A, (A-B) + A, 2(A - B) + A, \dots (k-1)(A - B) + A$$$. Since $$$(k-1)(A-B) + A = N - 1$$$, the second list may be rewritten backwards as $$$N - 1, N - 1 - (A - B), N - 1 - 2(A - B), \dots N - 1 - (k - 1)(A - B)$$$.

If we fix $$$A - B$$$ first and iterate over choices of $$$k$$$, the list of visited spots changes only by 2 elements each time we increment $$$k$$$. We can keep a record of visited spots and a total score and update them in constant time.

I used the same idea and got AC. Code

I think your idea is right because my idea is same to yours and i got AC.I think your boundary is wrong.