please explain me the approach to solve the problem http://mirror.codeforces.com/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
please explain me the approach to solve the problem http://mirror.codeforces.com/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
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 :)