| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
Could someone please provide an alternate solution with an explanation to this problem, or explain the official solution with more clarity (I only understand the first two lines)? I do not understand the logic behind precomputing "cost" or how the recurrence works.
Thanks in advance!
Here is my solution: https://pastebin.com/v8iWX27j
It is similar to the analysis solution. The idea is to first, loop through all 2^15 vertical subsets, and then to binary search on the answer. When we binary search on the answer we want to make sure that no area gets bigger than our current answer, which is how we assign the horizontal lines.
Someone ended up explaining the official sol to me, but upvote for the interesting sol! Is the runtime complexity better than the intended one (fairly sure it is a ratio of logN to N)?
This should be (N^2) (log 225000) (2^N) — probably a little slower, but more understandable to me at least. I set my binary search upper bound to 1e8, but it should really be 225000 based on the info that each grid cell is <= 1000. In this case it is slightly slower than the official solution as log_2 225000 is ~18.