### _Spongey's blog

By _Spongey, 4 months ago,

Last week, the Syrian Olympiad of Informatics finale took place, featuring a problem closely resembling the one found here Maximum Subarray Sum. The twist in this problem included an additional array, named B, where all elements $B_i \geq K$. The task was to find the Maximum Subarray Sum such that the sum of array $B$ for that subarray was less or equal than a given integer $K$.

For instance, with $N = 8$ and $K = 17$, given arrays: - Array A: -1 3 -2 5 3 -5 2 2 - Array B: 0 1 15 3 5 0 8 8

The correct answer wouldn't be 9, but 8 since there's a 15 blocking you from adding it. In the test, Also you can simply print 0 if the maximum answer is negative.

I approached this problem using the two-pointers technique, while I also explored a solution on USACO that utilized a set. My solution received an Accepted verdict on the CSES platform, but unfortunately, it failed a testcase on the SOI.

My AC Code on CSES

I may have wrote a different code cause I was sick, Idk, can someone telll me a case I fail?

• 0

 » 4 months ago, # | ← Rev. 2 →   0 Edited this a lot, sorry but Idk how to use the format correctly and ended up making Chat Gpt write me the blog sorryEdit: There was a preview...
 » 4 months ago, # | ← Rev. 2 →   0 This code got me 2 subtasks being: 1 — $A_i \geq 0$ 2 — There's only one negative Number in Array A
 » 5 weeks ago, # |   0 Because we didn't think about how you could implement your solution... Actually the idea is for every i 1<=i<=n you should take the lowest L such that the SUM for the range from l -> i in array b is smaller or equal K ... After you do that you are going to take the smallest prefix in the same range but in array A because there is a negative elements you can use two pointer for getting the range and a simple Data Structure for get the smallest prefix as SET