please explain me the approach to solve the problem http://codeforces.net/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 162 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | awoo | 158 |
6 | atcoder_official | 157 |
7 | nor | 155 |
7 | adamant | 155 |
9 | maroonrk | 152 |
10 | Dominater069 | 149 |
please explain me the approach to solve the problem http://codeforces.net/problemset/problem/332/B ..i read the editorial but couldnt understand the soln.. thanx in advance
Название |
---|
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 :)