Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

FCBLOK's blog

Codeforces Round #193 (Div. 2)
By FCBLOK, 10 years ago, In English

I have built a brute force solution to this problem but of course time limit exceeded monster has appeared!

please can anyone explain a solution or just give a hint for this problem, i have read the editorial but i didn't understand what is written.

Problem B

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

Comments Comments (2)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

You can see my solution at ....

Max[i].val is Max value of (Sum x[b]->x[b+k-1]) | if b in [i,n]. And Max[i].ind will be minimum index with this optimal Sum.

Using this you can remove second loop to find optimal b index in brute force solution. (Because if you selected index a, index b will be from [a+k] to [n])

The idea is same as editorial solution.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can do that:

1. Build the cumulative sum of the array (t[])

2. Go from left to right. Store in dpleft[i] the amount in the interval i, i-k. (dpleft[i] = t[i] — t[i-k])

3. Go from right to left. Store in dpright[i] the amount in the interval i, i+k. (dpright = t[i+k] — t[i])

4. Build the indexes in index left[] and index right[] and initialize with i (left) and n — i (right).

5. Go from k to n-k. If dpleft[i] > dpleft[i-1] then update indexleft[i] with i-k+1 (It means the max sum of any interval k that finishes at i from left to right, starts at position i-k+1) else update indexleft[i] with the max we have in indexleft[i-1] and update dpleft[i] with dpleft[i-1] (The previous position has the max value starting from 1 for any k interval)

6. Do the same now from right to left.

7. Go from k to n-k and take the max value of dpleft[i] + dpright[i]

This is my Solution.

→ Reply