ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1570. Eating High

Test 9
Posted by svr 10 Oct 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
Posted by svr 11 Oct 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.
Why it leads to TLE.

Edited by author 11.10.2007 13:59

Edited by author 11.10.2007 14:02
Re: Test 9
Posted by KIRILL(ArcSTUpid coder:) 11 Oct 2007 16:20
use memcpy()
Re: Test 9
Posted by Vladimir Yakovlev (USU) 11 Oct 2007 16:27
There is a solution with O(productivityness * number_of_dishes) time
Re: Test 9
Posted by Alexander Georgiev 7 Mar 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
Posted by svr 25 Mar 2008 22:50
I use more quick:
c1=(int *) malloc(20001*sizeof(int)) But Tle 16

Edited by author 25.03.2008 22:51
Re: Test 9
Posted by Fetisov Alex [USTU Frogs] 26 Mar 2008 21:59
Simple DP without any memory optimisations gives AC)
Re: Test 9
Posted by svr 28 Mar 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
Posted by Fetisov Alex [USTU Frogs] 31 Mar 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
Posted by Vedernikoff Sergey 1 Apr 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...