| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3845 |
| 2 | tourist | 3798 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3589 |
| 6 | Ormlis | 3532 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | Um_nik | 3450 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | Qingyu | 159 |
| 2 | -is-this-fft- | 159 |
| 4 | atcoder_official | 157 |
| 5 | Dominater069 | 156 |
| 6 | adamant | 154 |
| 7 | djm03178 | 151 |
| 8 | luogu_official | 149 |
| 9 | awoo | 148 |
| 10 | TheScrasse | 145 |
Question Link In this problem, I initially implemented a DP solution by defining the state and transition. However, it resulted in a "Memory Limit Exceeded" error. Surprisingly, when I simply interchanged the row and column while keeping the logic, states, and transitions the same, the solution was accepted.
Can someone explain why this happened?
You can see the Accepted Submission
Auto comment: topic has been updated by ilove_sundarKanya (previous revision, new revision, compare).
Auto comment: topic has been updated by ilove_sundarKanya (previous revision, new revision, compare).
Auto comment: topic has been updated by ilove_sundarKanya (previous revision, new revision, compare).
The reason is that vector needs to store some extra information, so just a vector without elements takes some memory.
The exact memory usage of an empty vector is implementation-dependent, but usually it's 24 bytes (64bit compiler, 3 pointers)
So for your AC solution we have around
((n + 1) * 8 + 24) * 2 + 24 = 160000088bytes and for MLE solution around(2 * 8 + 24) * (n + 1) + 24 = 400000064which is 2.5 times more