0 / 0 / 0
Регистрация: 15.03.2014
Сообщений: 3
|
||||||
1 | ||||||
Оптимизация олимпиадной задачи по программированию25.11.2014, 08:53. Показов 4786. Ответов 5
Метки нет (Все метки)
Есть задача:
Кликните здесь для просмотра всего текста
Ограничение времени на тест: 5 сек Ограничение памяти на тест: 256 Мб Условие Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r". Требуется написать программу, выполняющую данные команды. Формат входного файла Входной файл содержит целое число N, за которым следуют N целых чисел ai. Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел lj rj. Формат выходного файла Выходной файл должен содержать M целых чисел — результаты выполнения команд. Пример: Входной 5 1 2 3 4 5 3 1 3 2 5 3 5 Выходной 6 14 12 Написал рабочее решение на с++: Кликните здесь для просмотра всего текста
Но при исполнении тестирующая система выдает Time limit exceeded on test 15. Как можно оптимизировать программу или изменить алгоритм чтобы сократить время выполнения программы?
0
|
25.11.2014, 08:53 | |
Ответы с готовыми решениями:
5
Решение олимпиадной задачи (ч.2) Алгоритм решения олимпиадной задачи Оптимизация решения олимпиадной задачи Решение олимпиадной задачи |
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
25.11.2014, 11:31 | 2 |
Сообщение было отмечено letscodeqw как решение
Решение
letscodeqw, насчитай массив s[n], s[i] = сумма чисел a[0] + a[1] + ... + a[i]. (такой массив еще называют частичные или префиксные суммы). Дальше пойми как с помощью него ответить на запрос одним вычитанием.
1
|
_Ivana
|
25.11.2014, 12:00
#3
|
Не по теме: Некто Джоэл Спольски по этому поводу рассказывает следующий анекдот:
0
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
25.11.2014, 16:44 | 5 |
0
|
0 / 0 / 0
Регистрация: 15.03.2014
Сообщений: 3
|
|
29.11.2014, 14:54 [ТС] | 6 |
SlavaSSU, Спасибо. Помогло.
0
|
29.11.2014, 14:54 | |
29.11.2014, 14:54 | |
Помогаю со студенческими работами здесь
6
Решение олимпиадной задачи Решение олимпиадной задачи Решение олимпиадной задачи Понять условие олимпиадной задачи Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |