|
|
вернуться в форумIt seems that in test 9 M>20
All right,mistake
Edited by author 10.10.2007 13:39 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.
Why it leads to TLE.
Edited by author 11.10.2007 13:59
Edited by author 11.10.2007 14:02 use memcpy() 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 Simple DP without any memory optimisations gives AC) 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 Hm.. For each cost (calory) I had an array of the meals I used.. and no problems with memory 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... There is a solution with O(productivityness * number_of_dishes) time 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) |
|
|
