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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
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.
Название |
---|
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.
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.