fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. ll crr[10009],m,drr[10009],dp[10009],k,max1=600000000,h;
  5. ll recur(ll g);
  6. int d=0;
  7. int main()
  8. {
  9. 	int t;
  10. 	cin>>t;
  11. 	while(t--)
  12. 	{
  13. 		ll i,x,y,j,a,b,s,g=0,flag=0;
  14. 		cin>>a>>b;
  15. 		k=b-a;
  16. 		cin>>m;
  17. 		for(i=0;i<m;i++)
  18. 		{
  19. 			cin>>x>>y;
  20. 			crr[i]=y;
  21.             drr[i]=x;
  22.             /*if(y%2!=0)
  23.             {
  24.             	flag=1;
  25.             }*/
  26. 		}
  27.  
  28. 		for(i=0;i<=k;i++)
  29. 		dp[i]=max1;
  30. 	/*	if(flag==0 && k%2!=0)
  31. 		{
  32. 		cout<<"This is impossible."<<endl;
  33.             continue;
  34. 		}*/
  35. 		if(k==0)
  36. 		{
  37. 		cout<<"The minimum amount of money in the piggy-bank is 0."<<endl;	
  38. 		}
  39. 		else
  40. 		{
  41.         recur(0);
  42. 	if(dp[g]<600000000)
  43. 	cout<<"The minimum amount of money in the piggy-bank is "<<dp[0]<<"."<<endl;
  44. 	else
  45. 	cout<<"This is impossible."<<endl;
  46. 		}
  47.  
  48. 	}
  49. }
  50. ll recur(ll g)
  51. {
  52.  
  53. 	if(g>k){
  54. 	return max1;
  55.     }
  56.     if(g==k)
  57.     {
  58.     	return 0;
  59. 	}
  60. 	if(dp[g]!=max1){
  61. 		return dp[g];
  62. }
  63.  
  64. 	else
  65. {
  66. 	for(ll i=0;i<m;i++)
  67. 	{
  68. 		dp[g]=min(drr[i]+recur(g+crr[i]),dp[g]);
  69. 	}
  70. 	return dp[g];
  71. }
  72.  
  73. }
Success #stdin #stdout 0s 15352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eztC6b
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!