fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. int coin[]={1,5,10,25,50};
  8. int make;
  9. int dp[1000][1000];
  10.  
  11. int call(int i,int amount)
  12. {
  13. 	if(i>=5) {
  14. 		if(amount==0)
  15.             return 1;
  16. 		else
  17. 		    return 0;
  18. 	}
  19. 	if(dp[i][amount]!= -1)
  20.         return dp[i][amount];
  21.  
  22. 	int ret1=0,ret2=0;
  23.  
  24. 	if(amount-coin[i]>=0)
  25.         ret1 = call(i,amount-coin[i]);
  26.  
  27. 	ret2 = call(i+1,amount);
  28.  
  29. 	return dp[i][amount] = ret1+ret2;
  30.  
  31. }
  32.  
  33.  
  34. int main()
  35. {
  36.  
  37.  
  38.     memset(dp,-1,sizeof(dp));
  39.  
  40. 	while(cin>>make)
  41. 		cout<<call(0,make)<<endl;
  42.     return 0;
  43.  
  44. }
  45.  
Success #stdin #stdout 0s 7204KB
comments (?)
stdin
copy 
    0
    57
    129
    134
    239
    277
    300
    386
    393
    455
    510
    535
    568
    610
    637
    642
    790
    1426
    1446
    1498
    1503
    1590
    1600
    1624
    1635
    1647
    1691
    1722
    1931
    2116
    2261
    2455
    2547
    2663
    2703
    2707
    2765
    2827
    2915
    3258
    3349
    3915
    3960
    4261
    4691
    4800
    4862
    4928
    5001
    5151
    5246
    5331
    5376
    5559
    5826
    5853
    5975
    6071
    6168
    6239
    6321
    6423
    6482
    6543
    6620
    6796
    6962
    6973
    7026
    7104
    7355
    7414
    7481
    7489
stdout
copy 
1
62
558
628
4160
7098
9590
23124
24216
42230
64064
76384
93418
124124
144144
148421
327216
0
0
0
0
3406
3575
0
4186
0
0
0
11985
0
0
45
0
0
0
0
120
0
167
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
103
65
0
0
0
0
0
0
0
78
0
0
0
0
0
0
0
0
0
https://ideone.com/yzqdBF
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!