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. int dp[10001][2001];
  86. vp32 s1,s2,ss2;
  87. int vis[10001];
  88. int N,X,Y,a,b,mon,ans,from1,tmp;
  89.  
  90. int main(void) {
  91. 	fastio(0);
  92. 	cin >> N >> X >> Y;
  93. 	repn(i,N) { // Loops from 0 to N-1 (inclusive)
  94. 		cin >> a >> b;
  95. 		s1.pb(mp(a,i));
  96. 		s2.pb(mp(b,i));
  97. 		ss2.pb(mp(b,i)); // sorted version of market 2's list
  98. 	}
  99. 	sort(s1.begin(),s1.end());
  100. 	sort(ss2.begin(),ss2.end()); // sorted version of market 2's list
  101. 	repsn(i,1,N+1) { // Loops from 1 to N (inclusive)
  102. 		mon = Y, from1 = 0, tmp = 0;
  103. 		fill_n(vis,N+1,0);
  104. 		// DP to minimize spending in market 2
  105. 		repn(j,X+1) { // Loops from 0 to X (inclusive)
  106. 			if(j >= s1[i-1].fi) {
  107. 				from1++; // track max number of items that can be bought using only market 1
  108. 				dp[i][j] = min(s2[s1[i-1].se].fi+dp[i-1][j],dp[i-1][j-s1[i-1].fi]);
  109. 			} else {
  110. 				dp[i][j] = s2[s1[i-1].se].fi + dp[i-1][j];
  111. 			}
  112. 		}
  113. 		repsn(j,1,i+1) { // Loops from 1 to i (inclusive)
  114. 			vis[s1[j-1].se] = 1; // "blacklist" all purchased items
  115. 		}
  116. 		// If everything from market 2 is too expensive, buy only from market 1
  117. 		mon -= dp[i][X], tmp = (mon < 0) ? from1 : i;
  118. 		// greedy strategy using the leftover money in market 2
  119. 		if(mon >= 0) {
  120. 			repsn(j,1,N+1) { // Loops from 1 to N (inclusive)
  121. 				// Buy only the items that have not been bought, if there is enough money
  122. 				if(!vis[ss2[j-1].se] && mon >= ss2[j-1].fi) {
  123. 					mon -= ss2[j-1].fi;
  124. 					tmp++;
  125. 				}
  126. 			}
  127. 		}
  128. 		ans = max(ans,tmp);
  129. 	}
  130. 	cout << ans << "\n";
  131. 	return 0;
  132. }
Success #stdin #stdout 0s 94272KB
comments (?)
stdin
copy 
5 6 12
5 3
1 5
5 4
6 6
3 7
stdout
copy 
4
https://ideone.com/Vmm0lb
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!