please explain me the approach to solve the problem http://codeforces.me/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
please explain me the approach to solve the problem http://codeforces.me/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3312 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
| Name |
|---|



I didn't read editorial, but this is my solution :) Although, I don't think it will be different.
So your task is to find
non-intersecting segments with length k and maximum possible sum. First think we can notice is, that seqments are always exactly of length k. So you can precompute sum of sequence [a, a + k - 1] for each a. This can be easily done with one traverse of array. When we knew sum for sequence [a, a + k - 1] just add element xa + k and subtract element xa and you obtain sum for sequence [a + 1, a + k].
Now we can fix some b. We know sum for [b, b + k - 1], but what about first sequence. Where is best possible a. Well, simply is the sequence [a, a + k - 1] with biggest sum and a + k - 1 < b. But we cannot process all such a, because we will get solution with time complexity O(n2).
But we can also precompute the best a for interval [0, i] for every i using dp. Again, if some Si is the biggest sum of some sequence of length k in interval [0, i], than max(Si, sum([i - k + 2, i + 1])) is answer for interval [0, i + 1]. And we already compute value of sum([i - k + 2, i + 1]) in first transition.
With all of this we just go through all possible b and pick Sb - 1 as the best position for a. You can check my implementation (with som comments) here: 4270931. Time complexity of this solution is O(n).
I hope this is clear enough. If you got any additional questions just ask :)