I am getting MLE in test case 45 for C Question. I am not able to figure out the reason for it. Time Complexity and Space Complexity of my code are O(n^2) for each. Here's my submission. Can someone figure out my issue with my code ?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.11.2024 04:47:20 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
Don't save the inversions in a vector, that just uses extra time and memory. Try instead to apply the increments to the dp array directly, and in the end just loop over the array again and find the inversions instead of using the vector (a)
https://codeforces.net/contest/1678/submission/156390171
Thank you so much!! Was doing this silly thing
I observed that using one array of size 5000*5000 will be fine (takes about 195900 KB) but as soon as you u use two array of size 5000*5000 you will get MLE. This problem was tricky we get tle and mle check these two submission acc code mle code
Ok I see !!!!!!!