fork download
copy 
  1. // Li Hong Sheng Gabriel's Competitive Programming Template v2017.1
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <iomanip>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9. #include <list>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <climits>
  13. #include <queue>
  14. #include <cmath>
  15. #include <set>
  16. #include <cstdlib>
  17. #include <utility>
  18. #include <queue>
  19. #include <functional>
  20. #include <sstream>
  21. //#include <ext/pb_ds/assoc_container.hpp>
  22. //#include <ext/pb_ds/tag_and_trait.hpp>
  23.  
  24. //using namespace __gnu_pbds;
  25. using namespace std;
  26.  
  27. #define ll long long
  28. #define valid(r,c,rn,cn) (r >= 0 && c >= 0 && r < rn && c < cn)
  29. #define mp make_pair
  30. #define pb push_back
  31. #define sz size()
  32. #define pp pop()
  33. #define p32 pair<int,int>
  34. #define p64 pair<ll,ll>
  35. #define pdd pair<double,double>
  36. #define fi first
  37. #define se second
  38. #define tse se.fi
  39. #define th se.se
  40. #define tri pair<double,pdd>
  41. #define repn(i,e) for(int i = 0; i < e; i++)
  42. #define repsn(i,s,e) for(int i = s; i < e; i++)
  43. #define rrepn(i,s) for(int i = s; i >= 0; i--)
  44. #define rrepsn(i,s,e) for(int i = s; i >= e; i--)
  45. #define v64 vector<ll>
  46. #define v32 vector<int>
  47. #define vp64 vector<p64>
  48. #define vp32 vector<p32>
  49. #define vtri vector<tri>
  50. #define vprint(a,s) repn(k,s) cout << setw(3) << right << a[k] << " "; cout << endl
  51. #define mprint(a,rn,cn) repn(i,rn) { vprint(a[i],cn); cout << endl; }
  52. #define dmprint(a,s) repn(i,s) { cout << i << ": "; repn(j,a[i].sz) { cout << a[i][j] << " "; } cout << endl; }
  53. #define INF32 INT_MAX
  54. #define INF64 LLONG_MAX
  55. #define dsc greater
  56. #define pq priority_queue
  57. #define minhp pq<int,v32,dsc<int>>
  58. #define maxhp pq<int>
  59. #define um unordered_map
  60.  
  61. // Uncomment the include files, namespace and type to use
  62. //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> AVL;
  63. // Usage for AVL:
  64. // set functions, rank and select:
  65. //select: cout<<*X.find_by_order(>=1)<<endl;
  66. //rank: cout<<X.order_of_key(>=1)<<endl;
  67.  
  68. inline void scale(int x) { cout.precision(x); cout << fixed; }
  69. inline void pp32(p32 p) { cout << "( " << p.fi << ", " << p.se << " )" << endl; }
  70. inline void pp64(p64 p) { cout << "( " << p.fi << ", " << p.se << " )" << endl; }
  71. inline void ptri(tri t) { cout << "( " << t.fi << ", " << t.tse << ", " << t.th << " )" << endl; }
  72. double dist(pdd x,pdd y) { return sqrt((x.fi-y.fi)*(x.fi-y.fi)+(x.se-y.se)*(x.se-y.se)); }
  73. //int find(int x) { return (par[x]==x) ? x : par[x]=find(par[x]);}
  74. inline void fastio(int debug) {
  75. 	if(debug) {
  76. 		cout << "DEBUGGING MODE..." << endl;
  77. 		freopen("in","r",stdin);
  78. 	} else {
  79. 		ios_base::sync_with_stdio(false), cin.tie(0);
  80. 	}
  81. }
  82.  
  83. // End of Template
  84.  
  85. ll dp[2001][10001];
  86. vp32 s1,s2,ss2;
  87. int vis[10001];
  88. int N,X,Y,a,b,ans,tmp;
  89. ll mon;
  90.  
  91. int main(void) {
  92. 	fastio(0);
  93. 	cin >> N >> X >> Y;
  94. 	repn(i,N) { // Loops from 0 to N-1 (inclusive)
  95. 		cin >> a >> b;
  96. 		s1.pb(mp(a,i));
  97. 		s2.pb(mp(b,i));
  98. 		ss2.pb(mp(b,i)); // sorted version of market 2's list
  99. 	}
  100. 	sort(s1.begin(),s1.end());
  101. 	sort(ss2.begin(),ss2.end()); // sorted version of market 2's list
  102. 	mon = X;
  103. 	// Assume that we have the best answer using greedy choice from market 1 only
  104. 	repn(i,N) {
  105. 		if(mon < s1[i].fi) break;
  106. 		ans++, mon -= s1[i].fi;
  107. 	}
  108. 	repsn(i,1,N+1) { // Loops from 1 to N (inclusive)
  109. 		mon = Y, tmp = 0;
  110. 		fill_n(vis,N+1,0);
  111. 		// DP to minimize spending in market 2
  112. 		repn(j,X+1) { // Loops from 0 to X (inclusive)
  113. 			if(j >= s1[i-1].fi) {
  114. 				dp[i][j] = min(s2[s1[i-1].se].fi+dp[i-1][j],dp[i-1][j-s1[i-1].fi]);
  115. 			} else {
  116. 				dp[i][j] = s2[s1[i-1].se].fi + dp[i-1][j];
  117. 			}
  118. 		}
  119. 		repsn(j,1,i+1) { // Loops from 1 to i (inclusive)
  120. 			vis[s1[j-1].se] = 1; // "blacklist" all purchased items
  121. 		}
  122. 		// If everything from market 2 is too expensive, buy only from market 1
  123. 		mon -= dp[i][X], tmp = i;
  124. 		// greedy strategy using the leftover money in market 2
  125. 		if(mon >= 0) {
  126. 			repsn(j,1,N+1) { // Loops from 1 to N (inclusive)
  127. 				// Buy only the items that have not been bought, if there is enough money
  128. 				if(!vis[ss2[j-1].se] && mon >= ss2[j-1].fi) {
  129. 					mon -= ss2[j-1].fi;
  130. 					tmp++;
  131. 				}
  132. 			}
  133. 			ans = max(ans,tmp);
  134. 		}
  135. 	}
  136. 	cout << ans << "\n";
  137. 	return 0;
  138. }
Success #stdin #stdout 0s 172416KB
comments (?)
stdin
copy 
5 6 12
5 3
1 5
5 4
6 6
3 7
stdout
copy 
4
https://ideone.com/c3nc8Q
language:
C++14 (gcc 8.3)
created:
7 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!