fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define scan(x) scanf("%d",&x)
  4. #define print(x) printf("%d\n",x)
  5.  
  6. int main(){
  7.  
  8. 	int t;
  9. 	scan(t);
  10. 	while(t--){
  11. 		int p1,p2;
  12. 		scan(p1),scan(p2);
  13. 		p2-=p1;
  14. 		int n;
  15. 		scan(n);
  16. 		int P[n],W[n];
  17. 		for(int i=0;i<n;i++)
  18. 			scan(P[i]),scan(W[i]);
  19. 			bool V[p2+1];
  20. 			int val[p2+1];
  21. 			memset(V,0,sizeof(V));
  22. 			V[0]=1;
  23. 			val[0]=0;
  24. 			for(int i=1;i<=p2;i++)
  25. 				val[i]=INT_MAX;
  26.  
  27. 			for(int i=1;i<=p2;i++){
  28. 				for(int j=0;j<n;j++){
  29. 					if(i>=W[j]&&V[i-W[j]]){
  30. 						V[i]=1;
  31. 						val[i]=min(val[i],val[i-W[j]]+P[j]);
  32. 					}
  33. 				}
  34. 			}
  35. 			if(V[p2]){
  36. 				printf("The minimum amount of money in the piggy-bank is %d.\n",val[p2]);
  37. 			}else{
  38. 				printf("This is impossible.\n");
  39. 			}
  40.  
  41. 	}
  42. 	return 0;
  43. }
  44.  
  45.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
stdout
copy 
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
https://ideone.com/wALGfV
language:
C++14 (gcc 8.3)
created:
9 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!