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()

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)

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...