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