Post
by sunny_boy_in » Fri Aug 17, 2007 10:45 pm
My code gives TLE. Please help
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
int main()
{
while(1) {
int dec=0,frac=0;
scanf("%d.%d",&dec,&frac);
long value=(dec*100+frac);
if(value==0) break;
double val;
unsigned long long ways[7001][11];
memset(ways,0,sizeof(ways));
if(value%5!=0) {
ways[value][10]=0;
val=value/100.00;
}
else {
value/=5;
int coins[11]={1,2,4,10,20,40,100,200,400,1000,2000};
for(int i=0;i<11;i++) ways[0]=1;
for(int i=1;i<=value;i++) {
for(int j=0;j<11;j++) {
unsigned long long type1=(j==0?0:ways[j-1]);
unsigned long long type2=(i>=coins[j]?ways[i-coins[j]][j]:0);
ways[j]=type1+type2;
}
}
val=value/20.0;
}
printf("%6.2lf%17llu\n",val,ways[value][10]);
}
return 0;
}