|
|
|
|
|
|
|
| 1 Малявский Лазарь Сергеевич, 20 октября 2023 г. 22:24:01 |
| Тест 4: 10 2 15 1 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
|
|
| 2 Малявский Лазарь Сергеевич, 20 октября 2023 г. 22:16:18 |
| ДО действительно летит по времени
|
|
|
| 3 Парфенов Игорь Андреевич, 21 января 2021 г. 22:26:27 |
| Разреженная таблица (sparse table) работает за 0.15 секунд.
|
|
|
| 4 Дмитриев Дмитрий Андреевич, 29 марта 2020 г. 11:58:48 |
| Мультисет зашел... А почему ДО ловило TL на 10м тесте так и не понял(
|
|
|
| 5 Винк В В, 28 июня 2019 г. 17:58:34 |
| Решение динамикой здесь несложное. Самое интересное это найти эффективное решение подзадачи : поиск минимальных значений в смежных пересекающихся подмножествах. Заметны сходства с префикс-функцией. Тривиальное решение квадратичное, но с помощью дополнительной структуры данных и небольшого трюка оно становится линейным. Можно использовать мультисет, но это далеко не самый эффективный вариант это лишь O(L*log(L)). К тому же мультисет очень громоздкий и неповоротливый. Нужна двусторонняя очередь, я использовал для неё простой массив и две переменных для хранения идексов начала и конца очереди. Маленькая подсказка, например в очереди стоят числа : 7, 23, 26, 38, 51, 59 и нужно добавить в неё число 44. Для этого сначала удаляем числа 59 и 51, после этого добавляем в конец очереди 44.
|
|
|
| 6 Морозов Игорь Олегович, 30 июля 2014 г. 16:24:17 |
| Зашло O(N*L*log(R)). Когда нужно было ставить новую остановку на какую-то позицию, оптимальную позицию предыдущей остановки выбирал мультисетом. Но пришлось немного пошаманить, чтобы не делать лишних итераций.
|
|
|
| 7 Чак Норрис, 05 августа 2011 г. 7:46:07 |
| Ограничения r и R распространяются так же на расстояние от начала до первой остановки, а так же от последней до конца.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
