ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1570. Ужин на 45 этаже

Test 9
Послано svr 10 окт 2007 12:53
It seems that in test 9 M>20
All right,mistake

Edited by author 10.10.2007 13:39
Re: Test 9
Послано svr 11 окт 2007 13:59
This is the first problem in timus fo me when
DP gives TL(Tle15).In all world such strong tests
when DP used are absent as a rule. What parameters we have:
1. productivityness: from 0 to 30000;
2. number of dishes from 1 to 100
3. possible number of each dishes: from 1 to 100
Thus DP needs ~ 300000000 simple integer operations.

Edited by author 11.10.2007 13:59

Edited by author 11.10.2007 14:02
Re: Test 9
Послано KIRILL(ArcSTUpid coder:) 11 окт 2007 16:20
use memcpy()
Re: Test 9
Послано Vladimir Yakovlev (USU) 11 окт 2007 16:27
There is a solution with O(productivityness * number_of_dishes) time
Re: Test 9
Послано Alexander Georgiev 7 мар 2008 00:23
I used this solution and still got TLE on test 12. I couldn't accept it untill I reduced my used memory (use shorts instead of ints where possible, make the DP table as small as possible). Then I got accepted (0.8s on the toughest test)
Re: Test 9
Послано svr 25 мар 2008 22:50
I use more quick:
free(c);
c=c1;
c1=(int *) malloc(20001*sizeof(int)) But Tle 16

Edited by author 25.03.2008 22:51
Re: Test 9
Послано Fetisov Alex [USTU Frogs] 26 мар 2008 21:59
Simple DP without any memory optimisations gives AC)
Re: Test 9
Послано svr 28 мар 2008 20:28
I don't belive!
For Ac It was required to me a great carefulness
in the most internal loop.
For example: value k*c[i-1] I was forced to
precalculate as cc[k][i-1] and two characteristics
c and m where m- number of dishes to unite in
one as c*200-m
Re: Test 9
Послано Fetisov Alex [USTU Frogs] 31 мар 2008 00:04
Hm.. For each cost (calory) I had an array of the meals I used.. and no problems with memory
Re: Test 9
Послано Vedernikoff Sergey 1 апр 2008 13:51
My straightforward solution to the problem got AC within 0.234 sec without any optimizations/precalculations/so on. So, timelimit is quite huge and the only problem is in ineffective algos...