_Spongey's blog

By _Spongey, 4 months ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Edited this a lot, sorry but Idk how to use the format correctly and ended up making Chat Gpt write me the blog sorry

Edit: There was a preview...

4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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