fork download
copy 
  1. /* Template: By Jugal :) */
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. typedef long long int ll;
  5. typedef vector <int> vi;
  6. typedef vector <vi> vii;
  7. typedef pair<int,int> pii;
  8. typedef ll ft;
  9. #define get getchar_unlocked
  10. #define put putchar_unlocked
  11. #define pb push_back
  12. #define mp make_pair
  13. #define ff first
  14. #define ss second
  15. #define sz size()
  16. #define ln length()
  17. #define rep(i,n) for(int i=0;i<n;i++)
  18. #define ref(i,a,n) for(int i=a;i<=n;i++)
  19. #define reb(i,n,a) for(int i=n;i>=a;i--)
  20. #define all(a) a.begin(),a.end()
  21. #define gi(n) scanf("%d",&n)
  22. #define gii(n) scanf("%lld",&n)
  23. #define gc(c) scanf(" %c",&c)
  24. #define pi(n) printf("%d",n)
  25. #define pii(n) printf("%lld",n)
  26. #define pc(c) printf("%c",c)
  27. #define ps printf(" ")
  28. #define pn printf("\n")
  29. void gl(char *str) { char c; int i=0; if((c=get())!='\n') str[i++]=c; while((c=get())!='\n') str[i++]=c;str[i]='\0'; }
  30. void pl(char *str) { rep(i,strlen(str)) put(str[i]); }
  31. void gfi(ft &x) {
  32. register ft c = get(); x = 0; ft sn=1;
  33. for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;
  34. for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}
  35. x*=sn;
  36. }
  37.  
  38. ll val[1000],wgt[1000],dp[505][1005];
  39.  
  40. ll solve(ll n,ll w) {
  41. 	if(n==0 && w==0) return 0;
  42. 	if(n!=0 && w==0) return 0;
  43. 	if(n==0 && w!=0) return 10000000000ULL;
  44. 	if(dp[n][w]!=-1) return dp[n][w];
  45. 	ll ans=min(solve(n-1,w),(w-wgt[n]>=0)?(val[n]+solve(n,w-wgt[n])):solve(n-1,w));
  46. //	cout << ans << endl;
  47. 	return dp[n][w]=ans;
  48. }
  49.  
  50. int main() {
  51. 	ll t;
  52. 	gfi(t);
  53. 	while(t--) {
  54. 		ll n,e,w;
  55. 		gfi(e);gfi(w);
  56. 		w=w-e;
  57. 		gfi(n);
  58. 		ref(i,1,n) {
  59. 			gfi(val[i]);gfi(wgt[i]);
  60. 		}
  61. 		rep(i,n+3) rep(j,w+3) dp[i][j]=-1;
  62. 		ref(i,1,n) {
  63. 			ref(j,1,w) {
  64. 				solve(i,j);
  65. 			}
  66. 		}
  67. 		if(dp[n][w]>=10000000000ULL) cout << "This is impossible." << endl;
  68. 		else cout << "The minimum amount of money in the piggy-bank is " << dp[n][w] << "." << endl;
  69. 	}
  70. 	return 0;
  71. }
  72.  
Time limit exceeded #stdin #stdout 5s 7124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vgwOXX
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!