The time limit is 0.05 s But mine is 0.992 s .How can I optimize this code to get less than 0.5 s.
LightOj id 1006
#include<stdio.h>
int dp[10000];
long long unsigned int a, b, c, d, e, f;
int fn( long long unsigned int s )
{
for(int x=0;x<10000;x++)
{
dp[x]=-1;
}
if(s<6)
{
if( s == 0 ) return a;
if( s == 1 ) return b;
if( s == 2 ) return c;
if( s == 3 ) return d;
if( s == 4 ) return e;
if( s == 5 ) return f;
}
if(dp[s]!=-1)
return dp[s];
else {
dp[s]=( fn(s-1) + fn(s-2) + fn(s-3) + fn(s-4) + fn(s-5) + fn(s-6) );
return dp[s] ;
}
}
int main() {
long long unsigned int n;
int caseno = 0, cases;
scanf("%d", &cases);
while( cases-- ) {
scanf("%lld %lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f, &n);
printf("Case %d: %d\n", ++caseno,( fn(n) % 10000007) );
}
return 0;
}
I tried this way too
#include<stdio.h>
int dp[100];
long long unsigned int a, b, c, d, e, f;
int fn( long long unsigned int s ) {
dp[0]=a;
dp[1]=b;
dp[2]=c;
dp[3]=d;
dp[4]=e;
dp[5]=f;
for(int x=6;x<100;x++)
{
dp[x]=-1;
}
if(s<6){
if( s == 0 ) return a;
if( s == 1 ) return b;
if( s == 2 ) return c;
if( s == 3 ) return d;
if( s == 4 ) return e;
if( s == 5 ) return f;
}
if(dp[s]!=-1)
return dp[s];
else {
int q=0;
for(int y=1;y<=6;y++)
{
if(dp[s-y]!=-1)
q += dp[s-y];
else
{
dp[s-y]=fn(s-y);
q+=dp[s-y];
}
}
return q ;
}
}
int main() {
long long unsigned int n;int caseno = 0, cases;
scanf("%d", &cases);
while( cases-- ) {
scanf("%lld %lld %lld %lld %lld %lld %lld", &a, &b, &c, &d, &e, &f, &n);
printf("Case %d: %d\n", ++caseno,( fn(n) % 10000007) );
}
return 0;
}
But no development in time ,absolutely same …
Do I have to take totally different approach?
By the way,
The problem asked the same program (not optimized that time) to run and get output…
why I’m actually wasting so much time in this code…
Any help d be really really appreciated .
Thanks 